Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1762.html
1762. Buildings With an Ocean View
Level
Medium
Description
There are n
buildings in a line. You are given an integer array heights
of size n
that represents the heights of the buildings in the line.
The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height.
Return a list of indices (0indexed) of buildings that have an ocean view, sorted in increasing order.
Example 1:
Input: heights = [4,2,3,1]
Output: [0,2,3]
Explanation: Building 1 (0indexed) does not have an ocean view because building 2 is taller.
Example 2:
Input: heights = [4,3,2,1]
Output: [0,1,2,3]
Explanation: All the buildings have an ocean view.
Example 3:
Input: heights = [1,3,2,4]
Output: [3]
Explanation: Only building 3 has an ocean view.
Example 4:
Input: heights = [2,2,2,2]
Output: [3]
Explanation: Buildings cannot see the ocean if there are buildings of the same height to its right.
Constraints:
1 <= heights.length <= 10^5
1 <= heights[i] <= 10^9
Solution
For index i
where 0 <= i < n
, the building at index i
has an ocean view if and only if for all i < j < n
, there is heights[i] > heights[j]
. Obviously, the building at index n  1
has an ocean view.
Loop over heights
backwards and maintain the maximum height. For the building at index i
, if heights[i]
is greater than the maximum height, then the building has an ocean view. Update the maximum height using heights[i]
after determining whether the building at index i
has an ocean view.
Finally, return the indices of buildings that have an ocean view.

class Solution { public int[] findBuildings(int[] heights) { int length = heights.length; boolean[] oceanView = new boolean[length]; int count = 0; int maxHeight = 0; for (int i = length  1; i >= 0; i) { if (heights[i] > maxHeight) { oceanView[i] = true; count++; } maxHeight = Math.max(maxHeight, heights[i]); } int[] buildings = new int[count]; int index = 0; for (int i = 0; i < length; i++) { if (oceanView[i]) buildings[index++] = i; } return buildings; } } ############ class Solution { public int[] findBuildings(int[] heights) { int mx = 0; LinkedList<Integer> ans = new LinkedList<>(); for (int i = heights.length  1; i >= 0; i) { int v = heights[i]; if (mx < v) { ans.addFirst(i); mx = v; } } return ans.stream().mapToInt(i > i).toArray(); } }

// OJ: https://leetcode.com/problems/buildingswithanoceanview/ // Time: O(N) // Space: O(1) class Solution { public: vector<int> findBuildings(vector<int>& A) { vector<int> ans{(int)A.size()  1}; for (int i = A.size()  2; i >= 0; i) { if (A[i] > A[ans.back()]) ans.push_back(i); } reverse(begin(ans), end(ans)); return ans; } };

class Solution: def findBuildings(self, heights: List[int]) > List[int]: mx = 0 ans = [] for i in range(len(heights)  1, 1, 1): v = heights[i] if mx < v: ans.append(i) mx = v return ans[::1]

func findBuildings(heights []int) []int { mx := 0 ans := []int{} for i := len(heights)  1; i >= 0; i { v := heights[i] if mx < v { ans = append(ans, i) mx = v } } for i, j := 0, len(ans)1; i < j; i, j = i+1, j1 { ans[i], ans[j] = ans[j], ans[i] } return ans }

/** * @param {number[]} heights * @return {number[]} */ var findBuildings = function (heights) { let mx = 0; let ans = []; for (let i = heights.length  1; i >= 0; i) { const v = heights[i]; if (mx < v) { ans.push(i); mx = v; } } return ans.reverse(); };