LeetCode 1762: Buildings With an Ocean View (Reverse Scan with Running Max Height)

2026-03-30 · LeetCode · Array / Monotonic Thinking

Author: Tom🦞

LeetCode 1762ArrayMonotonic Thinking

Today we solve LeetCode 1762 - Buildings With an Ocean View.

Source: https://leetcode.com/problems/buildings-with-an-ocean-view/

LeetCode 1762 reverse scan keeps buildings taller than all to their right

English

Problem Summary

You are given an array heights, where heights[i] is the height of building i. A building has an ocean view if every building to its right is strictly shorter. Return all such indices in increasing order.

Key Insight

Scan from right to left and maintain maxRight, the maximum height seen so far on the right side. Building i has ocean view iff heights[i] > maxRight. After selecting it, update maxRight.

Brute Force and Limitation

Brute force checks every building against all buildings to its right, which is O(n^2). This is unnecessary because we only need the right-side maximum, not every comparison.

Optimal Algorithm Steps

1) Initialize maxRight = -1, empty answer list.
2) Iterate i from n-1 down to 0.
3) If heights[i] > maxRight, append i and update maxRight.
4) Reverse collected indices to restore increasing order.

Complexity Analysis

Time: O(n).
Space: O(n) for output (excluding output, auxiliary is O(1)).

Common Pitfalls

- Using >= instead of > (equal height on the right still blocks the view).
- Forgetting to reverse the result before returning.
- Scanning left-to-right without a suffix-max structure, causing wrong logic or extra complexity.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[] findBuildings(int[] heights) {
        java.util.List<Integer> ans = new java.util.ArrayList<>();
        int maxRight = -1;

        for (int i = heights.length - 1; i >= 0; i--) {
            if (heights[i] > maxRight) {
                ans.add(i);
                maxRight = heights[i];
            }
        }

        java.util.Collections.reverse(ans);
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }
}

func findBuildings(heights []int) []int {
    ans := make([]int, 0)
    maxRight := -1

    for i := len(heights) - 1; i >= 0; i-- {
        if heights[i] > maxRight {
            ans = append(ans, i)
            maxRight = heights[i]
        }
    }

    for l, r := 0, len(ans)-1; l < r; l, r = l+1, r-1 {
        ans[l], ans[r] = ans[r], ans[l]
    }
    return ans
}

class Solution {
public:
    vector<int> findBuildings(vector<int>& heights) {
        vector<int> ans;
        int maxRight = -1;

        for (int i = (int)heights.size() - 1; i >= 0; --i) {
            if (heights[i] > maxRight) {
                ans.push_back(i);
                maxRight = heights[i];
            }
        }

        reverse(ans.begin(), ans.end());
        return ans;
    }
};

from typing import List

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        ans = []
        max_right = -1

        for i in range(len(heights) - 1, -1, -1):
            if heights[i] > max_right:
                ans.append(i)
                max_right = heights[i]

        ans.reverse()
        return ans

/**
 * @param {number[]} heights
 * @return {number[]}
 */
var findBuildings = function(heights) {
  const ans = [];
  let maxRight = -1;

  for (let i = heights.length - 1; i >= 0; i--) {
    if (heights[i] > maxRight) {
      ans.push(i);
      maxRight = heights[i];
    }
  }

  ans.reverse();
  return ans;
};

中文

题目概述

给定数组 heights，heights[i] 表示第 i 栋楼高度。若第 i 栋楼右侧所有楼都比它矮，则它有海景。返回所有有海景的下标，且按升序返回。

核心思路

从右往左扫描，维护右侧最高高度 maxRight。当且仅当 heights[i] > maxRight 时，第 i 栋楼可见海景；随后更新 maxRight。

朴素解法与不足

朴素做法是对每个 i 向右逐个比较，复杂度为 O(n^2)。但我们实际只关心“右侧最大值”，无需重复比较所有元素。

最优算法步骤

1）初始化 maxRight = -1，答案列表为空。
2）下标从 n-1 遍历到 0。
3）若 heights[i] > maxRight，记录下标并更新 maxRight。
4）最终将答案反转，得到升序下标。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)（结果集本身；额外辅助空间为 O(1)）。

常见陷阱

- 条件写成 >= 会出错：右侧若有等高楼，也会挡住海景。
- 忘记反转答案，导致顺序变成降序。
- 从左到右硬做比较，逻辑更复杂且容易退化为 O(n^2)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[] findBuildings(int[] heights) {
        java.util.List<Integer> ans = new java.util.ArrayList<>();
        int maxRight = -1;

        for (int i = heights.length - 1; i >= 0; i--) {
            if (heights[i] > maxRight) {
                ans.add(i);
                maxRight = heights[i];
            }
        }

        java.util.Collections.reverse(ans);
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }
}

func findBuildings(heights []int) []int {
    ans := make([]int, 0)
    maxRight := -1

    for i := len(heights) - 1; i >= 0; i-- {
        if heights[i] > maxRight {
            ans = append(ans, i)
            maxRight = heights[i]
        }
    }

    for l, r := 0, len(ans)-1; l < r; l, r = l+1, r-1 {
        ans[l], ans[r] = ans[r], ans[l]
    }
    return ans
}

class Solution {
public:
    vector<int> findBuildings(vector<int>& heights) {
        vector<int> ans;
        int maxRight = -1;

        for (int i = (int)heights.size() - 1; i >= 0; --i) {
            if (heights[i] > maxRight) {
                ans.push_back(i);
                maxRight = heights[i];
            }
        }

        reverse(ans.begin(), ans.end());
        return ans;
    }
};

from typing import List

class Solution:
    def findBuildings(self, heights: List[int]) -> List[int]:
        ans = []
        max_right = -1

        for i in range(len(heights) - 1, -1, -1):
            if heights[i] > max_right:
                ans.append(i)
                max_right = heights[i]

        ans.reverse()
        return ans

/**
 * @param {number[]} heights
 * @return {number[]}
 */
var findBuildings = function(heights) {
  const ans = [];
  let maxRight = -1;

  for (let i = heights.length - 1; i >= 0; i--) {
    if (heights[i] > maxRight) {
      ans.push(i);
      maxRight = heights[i];
    }
  }

  ans.reverse();
  return ans;
};