寫在前
單調(diào)棧（monotone-stack）是指棧內(nèi)元素（棧底到棧頂）都是（嚴(yán)格）單調(diào)遞增或者單調(diào)遞減的曹动。
如果有新的元素入棧惩激，棧調(diào)整過程中 會(huì)將所有破壞單調(diào)性的棧頂元素出棧，并且出棧的元素不會(huì)再次入棧 侥蒙。由于每個(gè)元素只有一次入棧和出棧的操作，所以 單調(diào)棧的維護(hù)時(shí)間復(fù)雜度是O(n) 。
單調(diào)棧性質(zhì)：
- 單調(diào)棧里的元素具有單調(diào)性兴猩。
- 遞增（減）棧中可以找到元素左右兩側(cè)比自身小（大）的第一個(gè)元素早歇。
我們主要使用第二條性質(zhì)倾芝，該性質(zhì)主要體現(xiàn)在棧調(diào)整過程中，下面以自棧底到棧頂遞增為例（假設(shè)所有元素都是唯一）箭跳，當(dāng)新元素入棧晨另。
- 對(duì)于出棧元素來說：找到右側(cè)第一個(gè)比自身小的元素。
- 對(duì)于新元素來說：等待所有破壞遞增順序的元素出棧后谱姓，找到左側(cè)第一個(gè)比自身小的元素借尿。
1.單調(diào)棧結(jié)構(gòu)
問題描述：給定不含重復(fù)值的數(shù)組arr斤蔓，找到每個(gè)i位置左邊和右邊距離i最近的且值比i小的位置(沒有返回-1)癞蚕，返回所有的位置信息娃圆。
進(jìn)階問題：數(shù)組中含有重復(fù)值缤削。
示例：
arr = {3, 4, 1, 0}
{
{-1, 2},
{0, 2},
{-1, 3},
{-1, -1}
}
思路：常規(guī)時(shí)間復(fù)雜度O(n^2)實(shí)現(xiàn)簡(jiǎn)單耻瑟，每個(gè)位置向左和向右遍歷一遍暮屡。
單調(diào)棧實(shí)現(xiàn)：尋找兩邊距離arr[i]最近且arr[i]小的索引饮亏，保持棧頂?shù)綏５讍握{(diào)遞減（尋找比arr[i]大的值忆首，單調(diào)遞增）慨绳，棧中存放索引值掉冶。
對(duì)于進(jìn)階問題，區(qū)別在于重復(fù)索引值用集合進(jìn)行連接脐雪，棧中存放的是一個(gè)ArrayList厌小。注意兩點(diǎn)：
- arr[i]左邊應(yīng)該是上一個(gè)位置最晚加入的那個(gè)（如果有多個(gè)元素）
- 相等的情況直接在尾部加入，獲取值的時(shí)候循環(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;
}
代碼：進(jìn)階問題
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.下一個(gè)更大的元素（leetcode496-易）
題目描述：給你兩個(gè) 沒有重復(fù)元素 的數(shù)組 nums1 和 nums2 涨岁，其中nums1 是 nums2 的子集。
請(qǐng)你找出 nums1 中每個(gè)元素在 nums2 中的下一個(gè)比其大的值吉嚣。
nums1 中數(shù)字 x 的下一個(gè)更大元素是指 x 在 nums2 中對(duì)應(yīng)位置的右邊的第一個(gè)比 x 大的元素梢薪。如果不存在，對(duì)應(yīng)位置輸出 -1 尝哆。
示例：
輸入: nums1 = [4,1,2], nums2 = [1,3,4,2].
輸出: [-1,3,-1]
解釋:
對(duì)于 num1 中的數(shù)字 4 秉撇，你無法在第二個(gè)數(shù)組中找到下一個(gè)更大的數(shù)字，因此輸出 -1 。
對(duì)于 num1 中的數(shù)字 1 琐馆，第二個(gè)數(shù)組中數(shù)字1右邊的下一個(gè)較大數(shù)字是 3 规阀。
對(duì)于 num1 中的數(shù)字 2 ，第二個(gè)數(shù)組中沒有下一個(gè)更大的數(shù)字瘦麸，因此輸出 -1 谁撼。
思路：維護(hù)一個(gè)從棧頂?shù)綏５椎?strong>嚴(yán)格單調(diào)遞增的棧，先遍歷大數(shù)組記錄每個(gè)元素右邊第一個(gè)比當(dāng)前元素大的值滋饲，然后遍歷小數(shù)組輸出結(jié)果厉碟。這里用一個(gè)hashmap映射兩個(gè)數(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 個(gè)非負(fù)整數(shù)，用來表示柱狀圖中各個(gè)柱子的高度呵曹。每個(gè)柱子彼此相鄰款咖，且寬度為 1 。
求在該柱狀圖中奄喂，能夠勾勒出來的矩形的最大面積铐殃。
示例：
輸入: [2,1,5,6,2,3]
輸出: 10
思路：有了單調(diào)棧的基本認(rèn)識(shí)，我們可以遍歷每根柱子砍聊，以當(dāng)前柱子 i 的高度作為矩形的高背稼，那么矩形的寬度邊界即為向左找到第一個(gè)高度小于當(dāng)前柱體 i 的柱體，向右找到第一個(gè)高度小于當(dāng)前柱體 i 的柱體玻蝌。對(duì)于每個(gè)柱子我們都如上計(jì)算一遍以當(dāng)前柱子作為高的矩形面積，最終比較出最大的矩形面積即可词疼。
單調(diào)棧實(shí)現(xiàn)：尋找兩邊距離arr[i]最近且arr[i]小的索引俯树，保持棧頂?shù)綏５讍握{(diào)遞減，棧中存放索引值贰盗。
注意：頭0如果不添加许饿，尋找左邊元素需要判斷棧是否為空；尾0如果不添加舵盈，需要重新寫一個(gè)循環(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：首尾都擴(kuò)容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-難）
題目描述：給定一個(gè)僅包含 0 和 1 、大小為 rows x cols 的二維二進(jìn)制矩陣秽晚，找出只包含 1 的最大矩形瓦糟，并返回其面積。
示例：
輸入：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.
利用動(dòng)態(tài)規(guī)劃的思想先嬉，我們不需要重新遍歷之前走過的行轧苫，每遍歷一行更新一下矩陣的最大面積。計(jì)算當(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 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖含懊，計(jì)算按此排列的柱子，下雨之后能接多少雨水鳄袍。
示例：
輸入：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 個(gè)單位的雨水（藍(lán)色部分表示雨水）拗小。
思路：由示例我們可以看出上述可以劃分為四部分積水區(qū)域重罪，積水槽一定在兩個(gè)柱子之間。只有左右元素都大于當(dāng)前元素才能形成槽哀九，那么可以維護(hù)從棧底到棧頂單調(diào)遞減的單調(diào)棧：
- 這樣可以找到左邊第一個(gè)大于當(dāng)前元素的值剿配，當(dāng)右邊即將加入的值也大于它就形成了槽
- 棧中存放柱子對(duì)應(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)化：如果棧頂元素相等呼胚，則一直彈出，只留一個(gè)
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ū)間和的最大值（補(bǔ)充：字節(jié)高頻面試題）
題目描述：給定一個(gè)數(shù)組息裸，要求選出一個(gè)區(qū)間, 使得該區(qū)間是所有區(qū)間中經(jīng)過如下計(jì)算的值最大的一個(gè)：區(qū)間中的最小數(shù) * 區(qū)間所有數(shù)的和蝇更。注：數(shù)組中的元素都是非負(fù)數(shù)。
示例：
輸入兩行呼盆，第一行n表示數(shù)組長(zhǎng)度年扩，第二行為數(shù)組序列。輸出最大值访圃。
輸入
3
6 2 1
輸出
36
解釋：滿足條件區(qū)間是[6] = 6 * 6 = 36;
思路：最優(yōu)解單調(diào)棧厨幻，注意單調(diào)棧內(nèi)存的是索引
法1：使用暴力解，我們可以枚舉數(shù)組中的最小值腿时，然后向兩邊進(jìn)行擴(kuò)展况脆，找到第一個(gè)比x小的元素，在尋找區(qū)間的過程中計(jì)算區(qū)間和批糟。
法2：空間換時(shí)間格了，我們找邊界的過程中可以使用單調(diào)棧，每個(gè)元素只進(jìn)棧出棧一次跃赚，算法復(fù)雜度降到O(N)笆搓。這里在計(jì)算區(qū)間和時(shí)可以使用前綴和性湿。
代碼：
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-中）
題目描述：給定一個(gè)整數(shù)數(shù)組 arr算墨，找到 min(b) 的總和宵荒，其中 b 的范圍為 arr 的每個(gè)（連續(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ù)組中的每一個(gè)數(shù)作為最小值的范圍绰沥，比如對(duì)于某個(gè)數(shù)nums[i]能夠最小值以這種形式表示：左邊連續(xù)m個(gè)數(shù)比nums[i]大篱蝇，右邊連續(xù)n個(gè)數(shù)比nums[i]大。
其實(shí)就是找以每個(gè)數(shù)左邊和右邊的最小值徽曲，中間的數(shù)一定都是大于當(dāng)前這個(gè)數(shù)的（已經(jīng)出棧）根據(jù)下標(biāo)計(jì)算出這兩個(gè)范圍零截，根據(jù)上述公式計(jì)算即可。注意秃臣，可以在尾部添加0涧衙，保證剩余元素可以被彈出計(jì)算哪工。
注意：在進(jìn)行計(jì)算時(shí)，先將每個(gè)元素轉(zhuǎn)成long型再計(jì)算弧哎，否則最后一個(gè)測(cè)試用例過不了雁比。
代碼：
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()]) {
// 每個(gè)棧頂元素作為最小值
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-中）
題目描述：請(qǐng)根據(jù)每日 氣溫 列表，重新生成一個(gè)列表撤嫩。對(duì)應(yīng)位置的輸出為：要想觀測(cè)到更高的氣溫偎捎，至少需要等待的天數(shù)。如果氣溫在這之后都不會(huì)升高序攘，請(qǐng)?jiān)谠撐恢糜?0 來代替茴她。
提示：氣溫 列表長(zhǎng)度的范圍是 [1, 30000]。每個(gè)氣溫的值的均為華氏度程奠，都是在 [30, 100] 范圍內(nèi)的整數(shù)丈牢。
示例：
給定一個(gè)列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，
你的輸出應(yīng)該是 [1, 1, 4, 2, 1, 1, 0, 0]瞄沙。
思路： 本題顯然是計(jì)算當(dāng)前元素與后邊第一個(gè)比他大的元素距離己沛，單調(diào)棧的典型性應(yīng)用。
- 當(dāng)前元素小于等于棧頂元素帕识，入棧
- 當(dāng)前元素大于棧頂元素泛粹，出棧，計(jì)算此時(shí)棧頂元素與下一個(gè)最大元素即當(dāng)前元素的距離
注意：本題棧內(nèi)元素可以不用出棧肮疗。
代碼：
public int[] dailyTemperatures(int[] temperatures) {
// 維護(hù)：從棧頂?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;
}
