第十章 單調棧part01
739. 每日溫度
今天正式開始單調棧黍析，這是單調棧一篇掃盲題目，也是經典題屎开。
大家可以讀題阐枣，思考暴力的解法，然后在看單調棧的解法奄抽。 就能感受出單調棧的巧妙
文章講解
思路
- 暴力解法：兩層for循環(huán)蔼两，leetcode上超時了
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int len = temperatures.length;
int[] result = new int[len];
for(int i = 0; i < len; i++){
for(int j = i + 1; j < len; j++){
if(temperatures[j] > temperatures[i]){
result[i] = j - i;
break;
}
}
}
return result;
}
}
-
為什么想到使用單調棧
- 通常是一維數(shù)組，要尋找任一個元素的右邊或者左邊第一個比自己大或者小的元素的位置逞度，此時我們就要想到可以用單調棧了额划。時間復雜度為O(n)。
-
單調棧的原理
- 單調棧的本質是空間換時間档泽，因為在遍歷的過程中需要用一個棧來記錄右邊第一個比當前元素高的元素俊戳，優(yōu)點是整個數(shù)組只需要遍歷一次揖赴。
- 更直白來說，就是用一個棧來記錄我們遍歷過的元素抑胎，因為我們遍歷數(shù)組的時候燥滑，我們不知道之前都遍歷了哪些元素，以至于遍歷一個元素找不到是不是之前遍歷過一個更小的阿逃，所以我們需要用一個容器（這里用單調棧）來記錄我們遍歷過的元素铭拧。
在使用單調棧的時候首先要明確如下幾點：
單調棧里存放的元素是什么？
單調棧里只需要存放元素的下標i就可以了恃锉，如果需要使用對應的元素搀菩，直接T[i]就可以獲取。單調棧里元素是遞增呢破托？ 還是遞減呢肪跋？
- 注意以下講解中，順序的描述為 從棧頭到棧底的順序炼团。
- 這里我們要使用遞增循序（再強調一下是指從棧頭到棧底的順序）澎嚣，因為只有遞增的時候，棧里要加入一個元素i的時候瘟芝，才知道棧頂元素在數(shù)組中右面第一個比棧頂元素大的元素是i。
- 即：如果求一個元素右邊第一個更大元素褥琐，單調棧就是遞增的锌俱，如果求一個元素右邊第一個更小元素，單調棧就是遞減的敌呈。
使用單調棧主要有三個判斷條件贸宏。
- 當前遍歷的元素T[i]小于棧頂元素T[st.top()]的情況
- 當前遍歷的元素T[i]等于棧頂元素T[st.top()]的情況
- 當前遍歷的元素T[i]大于棧頂元素T[st.top()]的情況
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int len = temperatures.length;
int[] result = new int[len];
// 使用Deque來作為棧
Deque<Integer> stack = new LinkedList<>();
// 將第一個元素的索引壓入棧中，以便從第二個元素開始進行比較磕洪。
// 實際上吭练，這一步在邏輯上是多余的，并不需要顯式地初始化棧析显，可以直接從第一個元素開始循環(huán)處理鲫咽。
stack.push(0);
for(int i = 1; i < len; i++){
//情況一：當前溫度小于棧頂溫度,將當前索引壓入棧中。
if(temperatures[i] < temperatures[stack.peek()]){
stack.push(i);
//情況二：當前溫度等于棧頂溫度,將當前索引壓入棧中谷异。
}else if(temperatures[i] == temperatures[stack.peek()]){
stack.push(i);
//情況三：當前溫度大于棧頂溫度,循環(huán)彈出棧頂元素分尸，并計算當前索引與棧頂索引的差值，存入 result 數(shù)組對應的位置歹嘹。然后將當前索引壓入棧中箩绍。
}else{
while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
result[stack.peek()] = i - stack.peek();
stack.pop();
}
stack.push(i);
}
}
return result;
}
}
精簡代碼
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int len = temperatures.length;
int[] result = new int[len];
// 使用Deque來作為棧
Deque<Integer> stack = new LinkedList<>();
for(int i = 0; i < len; i++){
while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
result[stack.peek()] = i - stack.peek();
stack.pop();
}
stack.push(i);
}
return result;
}
}
496.下一個更大元素 I
思路
- 本題則是說nums1 是 nums2的子集，找nums1中的元素在nums2中下一個比當前元素大的元素尺上。
- 從題目示例中我們可以看出最后是要求nums1的每個元素在nums2中下一個比當前元素大的元素材蛛，那么就要定義一個和nums1一樣大小的數(shù)組result來存放結果圆到。
- result數(shù)組初始化：題目說如果不存在對應位置就輸出 -1 ，所以result數(shù)組如果某位置沒有被賦值卑吭，那么就應該是是-1构资，所以就初始化為-1。
- 題目說沒有重復元素陨簇，就可以用Map做映射吐绵。哈希表 hashMap 記錄 nums1 中每個元素在 nums2 中的位置，以便快速查找和更新結果河绽。
- 棧頭到棧底的順序己单，要從小到大，也就是保持棧里的元素為遞增順序耙饰。只要保持遞增纹笼，才能找到右邊第一個比自己大的元素。其實遞減棧就是求右邊第一個比自己小的元素了苟跪。
三種情況
注意廷痘，棧里的元素是nums2里的元素下標
- 情況一：當前遍歷的元素T[i]小于棧頂元素T[st.top()]的情況
滿足從棧頭到棧底遞增的情況，所以直接入棧件已； - 情況二：當前遍歷的元素T[i]等于棧頂元素T[st.top()]的情況
滿足從棧頭到棧底遞增的情況笋额，所以直接入棧； - 情況三：當前遍歷的元素T[i]大于棧頂元素T[st.top()]的情況
找到了右邊第一個比自己大的元素篷扩，不滿足從棧頭到棧底遞增的情況兄猩；
所以要先判斷棧頂元素在map中是否出現(xiàn)過，如果出現(xiàn)過就要找到這個元素在nums1中的下標鉴未，棧中其他元素出棧枢冤，把下標i加入棧，更新結果铜秆；
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
// 初始化棧和哈希表：
// 棧 temp 用于存儲 nums2 中的索引淹真，棧中的元素按 nums2 中對應值從大到小排列。
Stack<Integer> temp = new Stack<>();
int len1 = nums1.length;
int[] result = new int[len1];
Arrays.fill(result, -1); // 初始化結果數(shù)組连茧，默認值為 -1
// 哈希表 hashMap 記錄 nums1 中每個元素在 nums2 中的位置核蘸，以便快速查找和更新結果。
HashMap<Integer, Integer> hashMap = new HashMap<>();
for(int i = 0; i < len1; i++){
hashMap.put(nums1[i], i);
}
// 初始化棧
temp.add(0);
// 遍歷nums2
// 對于每個 nums2[i]梅屉，如果它小于等于棧頂元素的值值纱，直接將其索引入棧。
// 如果它大于棧頂元素的值坯汤，說明找到了棧頂元素的下一個更大元素虐唠。不斷彈出棧頂元素，直到棧為空或棧頂元素不再小于當前值惰聂，同時更新結果數(shù)組疆偿。
for(int i = 1; i < nums2.length; i++){ //在不精簡的代碼中遍歷從1開始咱筛，因為前面初始化棧了，手動將 nums2 的第一個元素索引 0 壓入棧中杆故。因此迅箩，后續(xù)遍歷從索引 1 開始，以避免重復處理第一個元素处铛。
if(nums2[i] <= nums2[temp.peek()]){
temp.add(i);
}else{
while(!temp.isEmpty() && nums2[i] > nums2[temp.peek()]){
if(hashMap.containsKey(nums2[temp.peek()])){
int index = hashMap.get(nums2[temp.peek()]);
result[index] = nums2[i];
}
temp.pop();
}
temp.push(i);
}
}
return result;
}
}
// 優(yōu)化版本
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
// 初始化棧和哈希表：
// 棧 temp 用于存儲 nums2 中的索引饲趋，棧中的元素按 nums2 中對應值從大到小排列。
Stack<Integer> temp = new Stack<>();
int len1 = nums1.length;
int[] result = new int[len1];
Arrays.fill(result, -1); // 初始化結果數(shù)組撤蟆，默認值為 -1
// 哈希表 hashMap 記錄 nums1 中每個元素在 nums2 中的位置奕塑，以便快速查找和更新結果。
HashMap<Integer, Integer> hashMap = new HashMap<>();
for(int i = 0; i < len1; i++){
hashMap.put(nums1[i], i);
}
// 遍歷nums2
// 對于每個 nums2[i]家肯，如果它小于等于棧頂元素的值龄砰，直接將其索引入棧。
// 如果它大于棧頂元素的值讨衣，說明找到了棧頂元素的下一個更大元素换棚。不斷彈出棧頂元素，直到棧為空或棧頂元素不再小于當前值反镇，同時更新結果數(shù)組固蚤。
for(int i = 0; i < nums2.length; i++){
while(!temp.isEmpty() && nums2[i] > nums2[temp.peek()]){
if(hashMap.containsKey(nums2[temp.peek()])){
int index = hashMap.get(nums2[temp.peek()]);
result[index] = nums2[i];
}
temp.pop();
}
temp.push(i);
}
return result;
}
}
503.下一個更大元素II
如何處理循環(huán)數(shù)組
- 將兩個nums數(shù)組拼接在一起，使用單調棧計算出每一個元素的下一個最大值愿险，最后再把結果集即result數(shù)組resize到原數(shù)組大小就可以了颇蜡。
- 這種寫法確實比較直觀，但做了很多無用操作辆亏，例如修改了nums數(shù)組，而且最后還要把result數(shù)組resize回去鳖目。resize倒是不費時間扮叨，是O(1)的操作，但擴充nums數(shù)組相當于多了一個O(n)的操作领迈。
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] extendedNums = new int[2 * n];
System.arraycopy(nums, 0, extendedNums, 0, n);
System.arraycopy(nums, 0, extendedNums, n, n);
int[] result = new int[2 * n];
Arrays.fill(result, -1);
if (n == 0) return result;
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
for (int i = 1; i < extendedNums.length; i++) {
if (extendedNums[i] < extendedNums[stack.peek()]) {
stack.push(i);
} else if (extendedNums[i] == extendedNums[stack.peek()]) {
stack.push(i);
} else {
while (!stack.isEmpty() && extendedNums[i] > extendedNums[stack.peek()]) {
result[stack.pop()] = extendedNums[i];
}
stack.push(i);
}
}
return Arrays.copyOf(result, n);
}
}
- 其實也可以不擴充nums彻磁，而是在遍歷的過程中模擬走了兩邊nums。
class Solution {
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] result = new int[n];
Arrays.fill(result, -1);
if (n == 0) return result;
Deque<Integer> stack = new ArrayDeque<>();
stack.push(0);
for (int i = 1; i < n * 2; i++) {
int currentIndex = i % n;
if (nums[currentIndex] < nums[stack.peek()]) {
stack.push(currentIndex);
} else if (nums[currentIndex] == nums[stack.peek()]) {
stack.push(currentIndex);
} else {
while (!stack.isEmpty() && nums[currentIndex] > nums[stack.peek()]) {
result[stack.pop()] = nums[currentIndex];
}
stack.push(currentIndex);
}
}
return result;
}
}
- 單調棧的精簡版本狸捅，即三種情況都做了合并的操作
-
i % nums.size()
這里的 i 是一個在循環(huán)中不斷遞增的索引衷蜓。
nums.size() 是數(shù)組 nums 的長度。
i % nums.size() 計算 i 除以 nums.size() 的余數(shù)尘喝，這樣可以確保索引始終在 0 到 nums.size() - 1 的范圍內磁浇。
這就實現(xiàn)了對數(shù)組的循環(huán)訪問。
class Solution {
public int[] nextGreaterElements(int[] nums) {
if(nums == null || nums.length <= 1) return new int[]{-1};
int len = nums.length;
int[] result = new int[len];
Arrays.fill(result, -1);
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < 2 * len; i++){
// 計算當前元素在 nums 數(shù)組中的實際索引
int currentIndex = i % len;
while(!stack.isEmpty() && nums[currentIndex] > nums[stack.peek()]){
result[stack.peek()] = nums[currentIndex];
stack.pop();
}
stack.push(currentIndex);
}
return result;
}
}
