Leetcode - 1762. Buildings With an Ocean View

문제

건물높이를 나타내는 배열이 주어짐. 건물 맨 오른쪽에 바다가 있다. 오션뷰인 건물의 index를 순서대로 나열하라. (오른쪽에 높이가 같거나 큰 건물이 없는경우가 오션뷰)

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.

해결 O(N)

오른쪽에 다음 큰 값이 없는경우가 오션뷰이므로, monotonic stack으로 구할수있다. decreasing monotonic stack을 구현하면 최종 스택에 남는 값이 정답이된다. 최종 답은 pop순서의 역순이 되어야하므로 stack대신 편의상 deque을 써보았다.

class Solution {
public:
    vector<int> findBuildings(vector<int>& heights) {
        vector<int> ret;
        deque<pair<int, int>> stk;
        
        stk.push_back(make_pair(0, heights[0]));
        for (int cur = 1; cur < heights.size(); cur++) {
            // decreasing monotonic stack
            while (!stk.empty() && heights[cur] >= stk.back().second) {
                stk.pop_back();
            }
            stk.push_back(make_pair(cur, heights[cur]));
        }
        while (!stk.empty()) {
            ret.push_back(stk.front().first); // deque을 쓴 이유
            stk.pop_front();
        }        
        return ret;
    }
};