寫在前

單調(diào)棧（monotone-stack）是指棧內(nèi)元素（棧底到棧頂）都是（嚴(yán)格）單調(diào)遞增或者單調(diào)遞減的。

如果有新的元素入棧，棧調(diào)整過程中 會將所有破壞單調(diào)性的棧頂元素出棧，并且出棧的元素不會再次入棧 。由于每個元素只有一次入棧和出棧的操作，所以 單調(diào)棧的維護時間復(fù)雜度是O(n) 。

單調(diào)棧性質(zhì)：

• 單調(diào)棧里的元素具有單調(diào)性。
• 遞增（減）棧中可以找到元素左右兩側(cè)比自身小（大）的第一個元素。

我們主要使用第二條性質(zhì)，該性質(zhì)主要體現(xiàn)在棧調(diào)整過程中，下面以自棧底到棧頂遞增為例（假設(shè)所有元素都是唯一），當(dāng)新元素入棧。

• 對于出棧元素來說：找到右側(cè)第一個比自身小的元素。
• 對于新元素來說：等待所有破壞遞增順序的元素出棧后，找到左側(cè)第一個比自身小的元素。

1.單調(diào)棧結(jié)構(gòu)

問題描述：給定不含重復(fù)值的數(shù)組arr，找到每個i位置左邊和右邊距離i最近的且值比i小的位置(沒有返回-1)，返回所有的位置信息。

進階問題：數(shù)組中含有重復(fù)值。

示例：

arr = {3, 4, 1, 0}
{
    {-1, 2},
    {0, 2},
    {-1, 3},
    {-1, -1}
}

思路：常規(guī)時間復(fù)雜度O(n^2)實現(xiàn)簡單，每個位置向左和向右遍歷一遍。

單調(diào)棧實現(xiàn)：尋找兩邊距離arr[i]最近且arr[i]小的索引，保持棧頂?shù)綏５讍握{(diào)遞減（尋找比arr[i]大的值，單調(diào)遞增），棧中存放索引值。

對于進階問題，區(qū)別在于重復(fù)索引值用集合進行連接，棧中存放的是一個ArrayList。注意兩點：

• arr[i]左邊應(yīng)該是上一個位置最晚加入的那個（如果有多個元素）
• 相等的情況直接在尾部加入，獲取值的時候循環(huán)的獲取該集合中的所有值（集合中元素值相等，索引值不同）

代碼：原問題

public int[][] getNearLessNoRepeat(int[] arr) {
    int[][] ans = new int[arr.length][2];
    Stack<Integer> stack = new Stack<>();
    // 遍歷數(shù)組，入棧
    for (int i = 0; i < arr.length; ++i) {
        while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
            int popIndex = stack.pop();
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
            ans[popIndex][0] = leftLessIndex;
            ans[popIndex][1] = i;
        }
        stack.push(i);
    }
    
    while (!stack.isEmpty()) {
        int popIndex = stack.pop();
        int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
        ans[popIndex][0] = leftLessIndex;
        // 說明該索引右邊沒有比當(dāng)前小的元素，有的話該索引在上邊循環(huán)就彈出了
        ans[popIndex][1] = -1;
    }
    return ans;
}

代碼：進階問題

public int[][] getNearLess(int[] arr) {
    int[][] ans = new int[arr.length][2];
    Stack<List<Integer>> stack = new Stack<>();
    // 遍歷數(shù)組，入棧
    for (int i = 0; i < arr.length; ++i) {
        while (!stack.isEmpty() && arr[i] < arr[stack.peek().get(0)]) {
            List<Integer> popIs = stack.pop();
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
            for (int popi : popIs) {
                ans[popi][0] = leftLessIndex;
                ans[popi][1] = i;
            }
        }
        if (!stack.isEmpty() && arr[i] == arr[stack.peek().get(0)]) {
            stack.peek().add(Integer.valueOf(i));
        } else {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(i);
            stack.push(list);
        }
    }
    
    while (!stack.isEmpty()) {
        List<Integer> popIs = stack.pop();
        int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
        for (int popi : popIs) {
            ans[popi][0] = leftLessIndex;
            ans[popi][1] = -1;
        }
    }
    return ans;
}

2.下一個更大的元素（leetcode496-易）

題目描述：給你兩個 沒有重復(fù)元素 的數(shù)組 nums1 和 nums2 ，其中nums1 是 nums2 的子集。

請你找出 nums1 中每個元素在 nums2 中的下一個比其大的值。

nums1 中數(shù)字 x 的下一個更大元素是指 x 在 nums2 中對應(yīng)位置的右邊的第一個比 x 大的元素。如果不存在，對應(yīng)位置輸出 -1 。

示例：

輸入: nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出: [-1,3,-1]
解釋:
    對于 num1 中的數(shù)字 4 ，你無法在第二個數(shù)組中找到下一個更大的數(shù)字，因此輸出 -1 。
    對于 num1 中的數(shù)字 1 ，第二個數(shù)組中數(shù)字1右邊的下一個較大數(shù)字是 3 。
    對于 num1 中的數(shù)字 2 ，第二個數(shù)組中沒有下一個更大的數(shù)字，因此輸出 -1 。

思路：維護一個從棧頂?shù)綏５椎?strong>嚴(yán)格單調(diào)遞增的棧，先遍歷大數(shù)組記錄每個元素右邊第一個比當(dāng)前元素大的值，然后遍歷小數(shù)組輸出結(jié)果。這里用一個hashmap映射兩個數(shù)組的元素，棧中元素這里仍是索引，也可用元素。

代碼：

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Stack<Integer> stack = new Stack<>();
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums2.length; ++i) {
        while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
            int cur = stack.pop();
            int rightMaxIdx = i;
            map.put(nums2[cur], nums2[rightMaxIdx]);
        }
        stack.push(i);
    }
    
    int[] ans = new int[nums1.length];
    for (int j = 0; j < nums1.length; ++j) {
        ans[j] = map.getOrDefault(nums1[j], -1);
    }
    return ans;
}

3.柱狀圖中最大的矩形（leetcode84-難）

問題描述：給定 n 個非負(fù)整數(shù)，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。

求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。

示例：

輸入: [2,1,5,6,2,3]
輸出: 10

思路：有了單調(diào)棧的基本認(rèn)識，我們可以遍歷每根柱子，以當(dāng)前柱子 i 的高度作為矩形的高，那么矩形的寬度邊界即為向左找到第一個高度小于當(dāng)前柱體 i 的柱體，向右找到第一個高度小于當(dāng)前柱體 i 的柱體。對于每個柱子我們都如上計算一遍以當(dāng)前柱子作為高的矩形面積，最終比較出最大的矩形面積即可。

單調(diào)棧實現(xiàn)：尋找兩邊距離arr[i]最近且arr[i]小的索引，保持棧頂?shù)綏５讍握{(diào)遞減，棧中存放索引值。

注意：頭0如果不添加，尋找左邊元素需要判斷棧是否為空；尾0如果不添加，需要重新寫一個循環(huán)彈出棧內(nèi)元素。

代碼：原問題

class Solution {

    // 單調(diào)棧（棧底到棧頂單調(diào)遞增）
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Deque<Integer> stack = new LinkedList<>();
        int ans = 0;

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                int curIndex = stack.pop();

                while (!stack.isEmpty() && heights[stack.peek()] == heights[curIndex]) {
                    stack.pop();
                }
                int leftIndex = stack.isEmpty() ? -1 : stack.peek();
                ans = Math.max(ans, (i - leftIndex - 1) * heights[curIndex]);
            }
            stack.push(i);
        }

        while (!stack.isEmpty()) {
            int curIndex = stack.pop();
            while (!stack.isEmpty() && heights[stack.peek()] == heights[curIndex]) {
                stack.pop();
            }
            
            int width = stack.isEmpty() ? n : n - stack.peek() - 1;
            ans = Math.max(ans, width * heights[curIndex]);
        }
        return ans;
    } 

    // 優(yōu)化1：添加尾0(推薦)
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        heights = Arrays.copyOf(heights, n + 1);
        Deque<Integer> stack = new LinkedList<>();
        int ans = 0;

        for (int i = 0; i < n + 1; i++) {
            while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                int curIndex = stack.pop();

                while (!stack.isEmpty() && heights[stack.peek()] == heights[curIndex]) {
                    stack.pop();
                }
                int leftIndex = stack.isEmpty() ? -1 : stack.peek();
                ans = Math.max(ans, (i - leftIndex - 1) * heights[curIndex]);
            }
            stack.push(i);
        }
        return ans;
    }

    // 優(yōu)化2：首尾都擴容0
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int[] tmp = new int[n + 2];
        System.arraycopy(heights, 0, tmp, 1, n);
        Deque<Integer> stack = new LinkedList<>();
        int ans = 0;

        for (int i = 0; i < n + 2; i++) {
            while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {
                int curIndex = stack.pop();

                while (!stack.isEmpty() && tmp[stack.peek()] == tmp[curIndex]) {
                    stack.pop();
                }
                int leftIndex = stack.peek();
                ans = Math.max(ans, (i - leftIndex - 1) * tmp[curIndex]);
            }
            stack.push(i);
        }
        return ans;
    }
}

4. 最大矩形（leetcode85-難）

題目描述：給定一個僅包含 0 和 1 、大小為 rows x cols 的二維二進制矩陣，找出只包含 1 的最大矩形，并返回其面積。

示例：

image.png

輸入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
輸出：6
解釋：最大矩形如上圖所示。

思路：本題與上題思路相同，這里我們每遍歷一行，更新代表柱子高度的函數(shù)heights。當(dāng)前單元為0，高度為0；當(dāng)前單元為1，高度+1.

利用動態(tài)規(guī)劃的思想，我們不需要重新遍歷之前走過的行，每遍歷一行更新一下矩陣的最大面積。計算當(dāng)前區(qū)域的最大矩形面積可以直接調(diào)用T84。

代碼：

public int maximalRectangle(char[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
    int row = matrix.length, col = matrix[0].length;
    int[] heights = new int[col];
    int ans = 0;

    for (int i = 0; i < row; ++i) {
        for (int j = 0; j < col; ++j) {
            if (matrix[i][j] == '0') heights[j] = 0;
            else ++heights[j];
        }
        ans = Math.max(ans, largestRectangleArea(heights));
    }
    return ans;
}

public int largestRectangleArea(int[] heights) {
    int[] tmp = new int[heights.length + 2];
    System.arraycopy(heights, 0, tmp, 1, heights.length);

    int maxArea = 0;
    Deque<Integer> stack = new LinkedList<>();
    for (int i = 0; i < tmp.length; ++i) {
        while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {
            int h = tmp[stack.pop()];
            maxArea = Math.max(maxArea, (i - stack.peek() - 1) * h);
        }
        stack.push(i);
    } 
    return maxArea;
}

5.接雨水（leetcode42-難）

題目描述：給定 n 個非負(fù)整數(shù)表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之后能接多少雨水。

示例：

輸入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
輸出：6
解釋：上面是由數(shù)組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個單位的雨水（藍(lán)色部分表示雨水）。

思路：由示例我們可以看出上述可以劃分為四部分積水區(qū)域，積水槽一定在兩個柱子之間。只有左右元素都大于當(dāng)前元素才能形成槽，那么可以維護從棧底到棧頂單調(diào)遞減的單調(diào)棧：

• 這樣可以找到左邊第一個大于當(dāng)前元素的值，當(dāng)右邊即將加入的值也大于它就形成了槽
• 棧中存放柱子對應(yīng)的索引值。
• 注意：高的取值，邊界較小的與當(dāng)前槽高度的差值

代碼：

class Solution {
    
    // 單調(diào)棧（從棧底到棧頂單調(diào)遞減）
    public int trap(int[] height) {
        if (height == null || height.length == 0) {
            return 0;
        }
        Deque<Integer> stack = new LinkedList<>();
        int ans = 0;

        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int curIndex = stack.pop();

                // 優(yōu)化：如果棧頂元素相等，則一直彈出，只留一個
                while (!stack.isEmpty() && height[stack.peek()] == height[curIndex]) {
                    stack.pop();
                }

                if (!stack.isEmpty()) {
                    int leftIndex = stack.peek();
                    ans += (i - leftIndex - 1) * (Math.min(height[leftIndex], height[i]) - height[curIndex]);
                }
            }
            stack.push(i);
        }
        return ans;
    }
}

6.求區(qū)間最小數(shù)乘區(qū)間和的最大值（補充：字節(jié)高頻面試題）

題目描述：給定一個數(shù)組，要求選出一個區(qū)間, 使得該區(qū)間是所有區(qū)間中經(jīng)過如下計算的值最大的一個：區(qū)間中的最小數(shù) * 區(qū)間所有數(shù)的和。注：數(shù)組中的元素都是非負(fù)數(shù)。

示例：

輸入兩行，第一行n表示數(shù)組長度，第二行為數(shù)組序列。輸出最大值。

輸入
3
6 2 1
輸出
36
解釋：滿足條件區(qū)間是[6] = 6 * 6 = 36;

思路：最優(yōu)解單調(diào)棧，注意單調(diào)棧內(nèi)存的是索引

法1：使用暴力解，我們可以枚舉數(shù)組中的最小值，然后向兩邊進行擴展，找到第一個比x小的元素，在尋找區(qū)間的過程中計算區(qū)間和。

法2：空間換時間，我們找邊界的過程中可以使用單調(diào)棧，每個元素只進棧出棧一次，算法復(fù)雜度降到O(N)。這里在計算區(qū)間和時可以使用前綴和。

代碼：

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class Solution004 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        int i = 0;
        while (n-- > 0) {
            nums[i++] = sc.nextInt();
        }
//        System.out.println(solution(nums));
        System.out.println(solution1(nums));
    }

    public static int solution(int[] nums) {
        int n = nums.length;
        int l = 0, r = 0;
        int sum = 0;
        int max = 0;

        for (int i = 0; i < n; i++) {
            sum = nums[i];
            l = i - 1;
            r = i + 1;
            while (l >= 0 && nums[l] >= nums[i]) {
                sum += nums[l--];
            }
            while (r < n && nums[r] >= nums[i]) {
                sum += nums[r++];
            }
            max = Math.max(max, sum * nums[i]);
        }
        return max;
    }

    // 單調(diào)棧優(yōu)化
    public static int solution1(int[] nums) {
        int n = nums.length;
        int l = 0, r = 0;
        int max = 0, cur = 0;
        Deque<Integer> stack = new LinkedList<>();

        //前綴和便于快速求區(qū)間和，例如求[l,r]區(qū)間和=dp[r+1]-dp[l]。l和r的取值范圍是[0,n)
        int[] sums = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }

        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
                cur = nums[stack.pop()];
                //l和r是邊界，因此區(qū)間是[l+1,r-1]，其區(qū)間和dp[r]-dp[l+1]
                l = stack.isEmpty() ? -1 : stack.peek();
                r = i;
                max = Math.max(max, cur * (sums[r] - sums[l + 1]));
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            cur = nums[stack.pop()];
            l = stack.isEmpty() ? -1 : stack.peek();
            r = n;
            max = Math.max(max, cur * (sums[r] - sums[l + 1]));
        }
        return max;
    }
}

7.子數(shù)組最小值之和（907-中）

題目描述：給定一個整數(shù)數(shù)組 arr，找到 min(b) 的總和，其中 b 的范圍為 arr 的每個（連續(xù)）子數(shù)組。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

示例：

輸入：arr = [3,1,2,4]
輸出：17
解釋：
子數(shù)組為 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
最小值為 3，1，2，4，1，1，2，1，1，1，和為 17。

思路： 這道題的本質(zhì)在于找到數(shù)組中的每一個數(shù)作為最小值的范圍，比如對于某個數(shù)nums[i]能夠最小值以這種形式表示：左邊連續(xù)m個數(shù)比nums[i]大，右邊連續(xù)n個數(shù)比nums[i]大。

其實就是找以每個數(shù)左邊和右邊的最小值，中間的數(shù)一定都是大于當(dāng)前這個數(shù)的（已經(jīng)出棧）根據(jù)下標(biāo)計算出這兩個范圍，根據(jù)上述公式計算即可。注意，可以在尾部添加0，保證剩余元素可以被彈出計算。

注意：在進行計算時，先將每個元素轉(zhuǎn)成long型再計算，否則最后一個測試用例過不了。

代碼：

private long mod = 1000000007;
public int sumSubarrayMins(int[] arr) {
    long ans = 0;
    int n = arr.length;
    arr = Arrays.copyOf(arr, n + 1);
    arr[n] = 0;
    Deque<Integer> stack = new LinkedList<>();
    for (int i = 0; i <= n; i++) {
        while (!stack.isEmpty() && arr[i] <= arr[stack.peek()]) {
            // 每個棧頂元素作為最小值
            int index = stack.pop();
            int lMin = !stack.isEmpty() ? stack.peek() : -1;
            int M = index - lMin - 1;
            int N = i - index - 1;
            ans += ((long)arr[index] * (M + 1) * (N + 1)) % mod;
        }
        stack.push(i);
    }
    return (int)(ans % mod);
}

8.每日溫度（739-中）

題目描述：請根據(jù)每日 氣溫 列表，重新生成一個列表。對應(yīng)位置的輸出為：要想觀測到更高的氣溫，至少需要等待的天數(shù)。如果氣溫在這之后都不會升高，請在該位置用 0 來代替。

提示：氣溫 列表長度的范圍是 [1, 30000]。每個氣溫的值的均為華氏度，都是在 [30, 100] 范圍內(nèi)的整數(shù)。

示例：

給定一個列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，
你的輸出應(yīng)該是 [1, 1, 4, 2, 1, 1, 0, 0]。

思路： 本題顯然是計算當(dāng)前元素與后邊第一個比他大的元素距離，單調(diào)棧的典型性應(yīng)用。

• 當(dāng)前元素小于等于棧頂元素，入棧
• 當(dāng)前元素大于棧頂元素，出棧，計算此時棧頂元素與下一個最大元素即當(dāng)前元素的距離

注意：本題棧內(nèi)元素可以不用出棧。

代碼：

public int[] dailyTemperatures(int[] temperatures) {
    // 維護：從棧頂?shù)綏５讎?yán)格遞增
    Deque<Integer> stack = new LinkedList<>();
    int n = temperatures.length;
    int[] ans = new int[n];

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int peak = stack.pop();
            ans[peak] = i - peak;
        }
        stack.push(i);
    }
    return ans;
}