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