單調堆疊（堆疊中的元素單調遞增或者單調遞減）----主要解決“The Next Greater Number”問題，尋找下一個更大或者下一個更小的數，
（以單調遞增為例）實作的思路就是：從后往前遍歷，如果當前元素比堆疊頂元素大，則堆疊頂元素出堆疊，再接著判斷，直到堆疊為慷訓者堆疊內的數大于當前元素為止；如果當前元素比堆疊頂元素小，則直接進堆疊，具體題目及代碼如下：
給你兩個 沒有重復元素 的陣列 nums1 和 nums2 ，其中nums1 是 nums2 的子集，
請你找出 nums1 中每個元素在 nums2 中的下一個比其大的值，
nums1 中數字 x 的下一個更大元素是指 x 在 nums2 中對應位置的右邊的第一個比 x 大的元素，如果不存在，對應位置輸出 -1 ，
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>(); //hash用來記錄比當前元素大的下一個元素，通過key，value的方式將二者系結，
Deque<Integer> stack = new ArrayDeque<Integer>();
for (int i = nums2.length - 1; i >= 0; --i) {
int num = nums2[i];
while (!stack.isEmpty() && num >= stack.peek()) { //如果當前元素大于堆疊頂元素，則堆疊頂元素出堆疊，直到堆疊為慷訓者堆疊頂元素大于當前元素為止，
stack.pop();
}
map.put(num, stack.isEmpty() ? -1 : stack.peek()); //此時的堆疊頂元素就是第一個比當前元素大的數，將兩者組合成（key，value）的形式保存起來
stack.push(num); //比堆疊頂小，直接進堆疊，
}
int[] res = new int[nums1.length];
for (int i = 0; i < nums1.length; ++i) {
res[i] = map.get(nums1[i]);
}
return res;
}
}
基本原理：
倒序保證了，只有后面的數比前面的數大才有機會保存在堆疊里，如果比前面的數小，那么在找The Next Greater Number時，是不可能輪到它的，所以每次進堆疊的操作，實際上就是在清楚，當前元素和下一個較大元素之間的較小的元素，就像在記錄“山頭”一樣，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/348654.html
標籤：其他
下一篇：Python入門的Hello