# Monotonic stack(單調棧/單調陣列)
Host - Al
Master - Jack
Interviewer - Brian
Candidate - Lyndon

## Mock Interview
https://docs.google.com/document/d/11sALw-uUXmNrhpTEvFDsFgs1jze90TVloHfP1kB30XI/edit

## 重點
1. 單調棧是用來找尋鄰近的元素
單調棧不僅用於確定數組的單調性，更多的是用來解決找尋與數組中元素鄰近的問題，例如尋找某元素右側的第一個比它大或小的元素。

2. 單調棧在推入元素時會維持其遞增或遞減的性質
當元素進入棧時，單調棧會通過不斷的彈出棧頂元素來確保它維持遞增或遞減的性質。

### 舉例來說

假設我們有一個數組
[2, 1, 3, 4, 0] 我們想知道每個元素右邊的第一個比它小的元素。

對於元素 2，它右邊的第一個比它小的元素是 1。
對於元素 1，它右邊沒有比它小的元素。
對於元素 3，它右邊的第一個比它小的元素是 0。
對於元素 4，它右邊的第一個比它小的元素是 0。
對於元素 0，它右邊沒有元素。
使用單調棧，我們可以簡單地得到答案為
[1,0,0,0,−1]

### 模板
以 nextSmaller 舉例

std::vector<int> nextSmallerElement(const std::vector<int>& nums) {
    std::vector<int> result(nums.size(), -1);
    std::stack<int> s;  // 存儲元素索引的單調棧

    for (int i = 0; i < nums.size(); ++i) {
        while (!s.empty() && nums[i] < nums[s.top()]) {
            int idx = s.top();
            s.pop();
            result[idx] = i;
        }
        s.push(i);
    }

    return result;
}

## 使用 deque 的單調隊列/棧
當我們討論單調棧時，實際上我們通常指的是一種特殊的數據結構，它在底層可以使用堆疊或隊列來實現。在某些情況下，使用雙端隊列 (deque) 作為底層結構會更加方便，因為它允許我們在前端和後端同時進行操作。

### 基本概念
單調隊列是一種數據結構，它可以在任一端插入或刪除元素，同時保持其內部元素的單調性（遞增或遞減）。

### 使用場景
滑動窗口中的最大/最小值問題。
某些需要快速找到當前元素之前/之後的最大/最小值的問題。

#include <iostream>
#include <vector>
#include <deque>

std::vector<int> slidingWindowMin(const std::vector<int>& nums, int k) {
    std::deque<int> dq;  // 存儲元素索引的單調隊列
    std::vector<int> result;

    for (int i = 0; i < nums.size(); ++i) {
        // 移除超出窗口的索引
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // 維持隊列的單調性
        while (!dq.empty() && nums[i] <= nums[dq.back()]) {
            dq.pop_back();
        }

        dq.push_back(i);

        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }

    return result;
}

int main() {
    std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    std::vector<int> result = slidingWindowMin(nums, k);

    for (int val : result) {
        std::cout << val << " ";
    }

    return 0;
}

## 練習
[496. Next Greater Element I ](https://leetcode.com/problems/next-greater-element-i/) =>[解答](https://hackmd.io/@jacklee20499/r1rYVakg6)
[739. Daily Temperatures](https://leetcode.com/problems/daily-temperatures/)=>[解答](https://hackmd.io/@jacklee20499/HkBvtSB0h)
[84. Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)=>[解答](https://hackmd.io/@jacklee20499/BJHqmnWkT)
[239. Sliding Window Maximum](https://leetcode.com/problems/sliding-window-maximum/)=>[解答](https://hackmd.io/@jacklee20499/r1amQrB16)

## 題目
[42. Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/) =>[解答](https://hackmd.io/@jacklee20499/BkQJl6ACn)
[856. Score of Parentheses](https://leetcode.com/problems/score-of-parentheses/) =>[解答](https://hackmd.io/@jacklee20499/HJtp4Jgl6)
[901. Online Stock Span](https://leetcode.com/problems/online-stock-span/) =>[解答](https://hackmd.io/@jacklee20499/ry34FzxxT)
[907. Sum of Subarray Minimums](https://leetcode.com/problems/sum-of-subarray-minimums/) =>[解答](https://hackmd.io/@jacklee20499/r1Gv9zeeT)
[1130. Minimum Cost Tree From Leaf Values](https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/) =>[解答](https://hackmd.io/@jacklee20499/rJvdUz-ea)
[1425. Constrained Subsequence Sum](https://leetcode.com/problems/constrained-subsequence-sum/) =>[解答](https://hackmd.io/@jacklee20499/B12loDzga)
[1475. Final Prices With a Special Discount in a Shop](https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop/) =>[解答](https://hackmd.io/@jacklee20499/rJCCdwGep)
[1671. Minimum Number of Removals to Make Mountain Array](https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array/) =>[解答](https://hackmd.io/@jacklee20499/r1beAcMlT)
[1673. Find the Most Competitive Subsequence](https://leetcode.com/problems/find-the-most-competitive-subsequence/) =>[解答](https://hackmd.io/@jacklee20499/rkS7pWQgp)
[1776. Car Fleet II](https://leetcode.com/problems/car-fleet-ii/) =>[解答](https://hackmd.io/@jacklee20499/HyJF98Xg6)
[2281. Sum of Total Strength of Wizards](https://leetcode.com/problems/sum-of-total-strength-of-wizards/) =>[解答](https://hackmd.io/@jacklee20499/rkdzk07eT)
[2289. Steps to Make Array Non-decreasing](https://leetcode.com/problems/steps-to-make-array-non-decreasing/) =>[解答](https://hackmd.io/@jacklee20499/SkO83zSlp)
[2398. Maximum Number of Robots Within Budget](https://leetcode.com/problems/maximum-number-of-robots-within-budget/) =>[解答](https://hackmd.io/@jacklee20499/rJgWLQBg6)
[2454. Next Greater Element IV](https://leetcode.com/problems/next-greater-element-iv/) =>[解答](https://hackmd.io/@jacklee20499/rksxOVrea)
[2735. Collecting Chocolates](https://leetcode.com/problems/collecting-chocolates/) =>[解答](https://hackmd.io/@jacklee20499/r1FiNsLea)
[2866. Beautiful Towers II](https://leetcode.com/problems/beautiful-towers-ii/) =>[解答](https://hackmd.io/@jacklee20499/HkqCm3keT)