Monotonic Stack 문제

숲사람·2022년 10월 2일
0

멘타트 컬렉션

목록 보기
5/13

Monotonic Stack 이란?

일련의 값에서 바로 다음 큰값이나, 바로 다음 작은 값을 구해야할 때 사용할 수 있는 Stack 풀이법.

  • increasing
    삽입하려는 값이 stack의 top보다 클때만 push, 삽입하려는 값보다 작은 값은 모두 stack에서 pop.
    배열에서 다음 작은값이 무엇인지 알아낼 수 있음.
  • decreasing
    삽입하려는 값이 stack의 top보다 작을 때만 push, 삽입하려는 값보다 큰값은 모두 stack에서 pop.
    배열에서 다음 큰값이 무엇인지 알 수 있음.

739. Daily Temperatures

문제

날짜별 온도가 담긴 배열이 주어진다. 각 날짜별로 온도가 처음으로 높아지는 날이 몇일 뒤인지 파악해라.

Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

해결

brute force(n^2) 해결외에 방법이 잘 떠오르지 않아서,해설을 보니 monotonic stack 기법을 사용하면 된다. temp배열을 하나씩 순회하면서 오늘온도가 스택의 top의 값보다 크면 top에 해당하는 날짜의 값을 계산할 수 있다. 그리고 마지막으로 오늘온도를 stack에 push한다. 이 기법을 잘 숙지하고 있으면 앞으로 유사유형에 사용가능할듯 -> Monotonic Stack

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<pair<int, int>> stk; // idx, temper
        
        stk.push(make_pair(0, temperatures[0]));
        temperatures[0] = 0;
        for (int i = 1; i < temperatures.size(); i++) {
            while (!stk.empty() && temperatures[i] > stk.top().second) {
                temperatures[stk.top().first] = i - stk.top().first;
                stk.pop();
            }
            stk.push(make_pair(i, temperatures[i]));
            temperatures[i] = 0;
        }
        return temperatures;
    }
    
};

아래는 stack에 index만 저장한 버전. 그런데 아래방법은 공간은 더 적게 사용하지만 속도가 더 느리게 나왔음.

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> stk; // idx, 
        vector<int> ans(temperatures.size(), 0);
        
        stk.push(0);
        for (int i = 1; i < temperatures.size(); i++) {
            while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
                ans[stk.top()] = i - stk.top();
                stk.pop();
            }
            stk.push(i);
        }
        return ans;
    }
    
};

1475. Final Prices With a Special Discount in a Shop

문제

가격이 적혀있는 배열이 주어진다. 현재 index보다 큰 index의 값중에 첫번째 작은가격의 값으로 현재 값을 할인 받는다면 최종 할인된 가격배열은?
가령 아래 예시에서 [0] index의 이후 index중에 [1]의 가격이 4이므로 [0]번의 할인된 가격은 8-4 가 된다.

Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation: 
For item 0 with price[0]=8 you will receive a discount equivalent to prices[1]=4, therefore, the final price you will pay is 8 - 4 = 4. 
For item 1 with price[1]=4 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 4 - 2 = 2. 
For item 2 with price[2]=6 you will receive a discount equivalent to prices[3]=2, therefore, the final price you will pay is 6 - 2 = 4. 
For items 3 and 4 you will not receive any discount at all.

해결

다음 작은 값을 찾는 문제이므로 Monotonic stack문제, incresing monotonic stack 으로 다음 배열을 찾고 할인가격을 계산.

소요시간 : 18min

class Solution {
public:
    vector<int> finalPrices(vector<int>& prices) {
        stack<pair<int, int>> disc; // idx, val
        
        disc.push(make_pair(0, prices[0]));
        for (int cur = 1; cur < prices.size(); cur++) {
            // incresing monotonic stack
            while (!disc.empty() && disc.top().second >= prices[cur]) {
                pair<int, int> check = disc.top();
                disc.pop();
                prices[check.first] -= prices[cur];
            }
            disc.push(make_pair(cur, prices[cur]));
        }
        return prices;
    }
};

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;
    }
};

42. Trapping Rain Water [H]

문제

높이값이 나열된 배열이 있다. 비가와서 물이 고일때, 최대 고인물(?)의 양은 얼마인가?

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

해결 - Monotonic Stack O(n) / O(n)

기본적으로 descreasing monotonic stack을 사용하여 풀 수 있다. stack에 top 높이가 작은 값만 push할 수 있다. 만약 현재 높이가 stack의 top보다 크다면, pop을 한다. stack에는 index를 push한다.

    ⬛️ 
⬛️  ⬛️
⬛️⬛️⬛️
1 0 2 <- 높이값

그런데 단순히 pop이 아니라, 조금 더 복잡한 계산을 해야한다. pop을 하는 경우의 형태는 위와 같이 U 구덩이모양의 형태밖에 없다. 스택의 top위치는 반드시 물이 고이는 위치다.(위 그림에서 높이가 0인지점) top이전 값은 top보다 무조건 높이가 높고(deceasing monotonic stack규칙에따라), 현재값도 top보다 무조건 높이가 높기 때문이다. 이 형태에서 고이는 물의 높이는 1과 2중 작은값인 1이 될것이다.

      ⬛️   
⬛️    ⬛️  
⬛️⬛️  ⬛️
⬛️⬛️⬛️⬛️
2 1 0 3 <- 높이값.

위와 같이 높이 h[]배열 값이 {2,1,0,3} 으로 주어진다고 하자. 아래의 동작을 수행하면 고인물의 양을 계산할 수 있다.

  • 먼저 높이 2를 갖는 h[0]의 인덱스 0를 push한다. 스택은 {[0]}
  • 그다음 h[1]높이가 top보다 작으므로 h[1]인덱스를 push 스택은 {[0], [1]}
  • 그다음 h[2]높이가 top보다 작으므로 h[2]인덱스를 push 스택은 {[0], [1], [2]}
  • 그 다음 h[3]높이가 top보다 크다. 따라서 top위치(h[2])에는 물이 고일것이다. 물이 고이는 높이는 h[3]과 스택내의 top바로 직전 높이 h[1]중에 작은 높이가 될것이다. 그리고 폭은 인덱스값 차이인 [3] - [1] - 1가 되어 높이*폭 = 1이 된다. 이 작업을 수행하면 아래와 같이 물이 고인다. 이 시점에 스택은 한번 pop되었기 때문에 {[0], [1]}
         ⬛️   
    ⬛️    ⬛️  
    ⬛️⬛️⬜️⬛️
    ⬛️⬛️⬛️⬛️
  • 현재 비교 대상인 h[3]의 높이가 여전히 스택 top값인 h[1]보다 높다. 따라서 pop및 위의 계산을 또 한번 수행한다. 높이: min(h[3], h[0]) - h[1], 그리고 폭은: [3]-[0]-1. 높이는 1 (2-1), 폭은 2, 따라서 물의 양은 2가 추가된다. 이 시점이 되면 아래와 같이 물이 추가로 찬다. 스택은 모두 pop이 되고, 현재 높이 h[3]이 push된다. 따라서 스택은 {[3]}
         ⬛️   
    ⬛️⬜️⬜️⬛️  
    ⬛️⬛️⬜️⬛️
    ⬛️⬛️⬛️⬛️

이어지는 높이가 주어져도 이 동작을 반복하면 고인물의 총량을 계산할 수 있다.
해설을 참고하였는데, 이 풀이를 이해 하는데 꽤나 오래걸렸다.

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> st; // index
        int hsize = height.size();
        int amount_water = 0;
        
        for (int i = 0; i < hsize; i++) {
            // if curr height >= then top of stack
            while (!st.empty() && height[i] >= height[st.top()]) {
                // -_-
                // 123   -> (3): curr height[i], (2): first st.top(), (3): second st.top()
                int u_shape_idx = st.top(); // the first st.top() is always 'U' shape position 
                st.pop();
                if (st.empty())
                    break;
                // this point st.top()'s height is always higher than height[u_shape_idx]
                int distance = i - st.top() - 1;
                int water_height = std::min(height[i], height[st.top()]) - height[u_shape_idx];
                amount_water += distance * water_height;
            }
            st.push(i);
        }
        return amount_water;
    }
};
profile
기록 & 정리 아카이브 용도 (보다 완성된 글은 http://soopsaram.com/documentudy)

0개의 댓글