main.cpp

// Source: https://leetcode.com/problems/buildings-with-an-ocean-view
// Title: Buildings With an Ocean View
// Difficulty: Medium
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 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 **(0-indexed)** 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 (0-indexed) 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.
// ```
//
// **Constraints:**
//
// - `1 <= heights.length <= 10^5`
// - `1 <= heights[i] <= 10^9`
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <algorithm>
#include <vector>

using namespace std;

// Loop from right to left, tracks the tallest building.
class Solution {
 public:
  vector<int> findBuildings(vector<int>& heights) {
    int n = heights.size();

    // Loop
    auto ans = vector<int>();
    auto maxHeight = 0;
    for (auto i = n - 1; i >= 0; --i) {
      auto height = heights[i];
      if (height > maxHeight) ans.push_back(i);
      maxHeight = max(maxHeight, height);
    }

    // Reverse
    reverse(ans.begin(), ans.end());

    return ans;
  }
};