單調(diào)棧題解
單調(diào)棧結(jié)構(gòu)
方法：單調(diào)棧
算法
這里維護(hù)一個(gè)單調(diào)遞增棧墩瞳，可以找到比當(dāng)前元素要小的元
約定：當(dāng)前元素 cur售滤，棧頂元素 top，出棧的棧頂元素 tempTop
- 遍歷數(shù)組
- 如果當(dāng)前元素大于棧頂元素悄雅，則入棧(入棧元素索引驱敲，而不是值)
- 否則，將棧頂元素出棧煤伟，此時(shí)癌佩，離 tempTop 左邊最近且值比 tempTop 小的就是當(dāng)前的棧頂元素 top木缝，離 tempTop 右邊最近且值比 tempTop 小的就是當(dāng)前元素 cur。 然后循環(huán)此過程围辙，直到第二步條件滿足我碟。
- 遍歷數(shù)組結(jié)束后，最后將棧內(nèi)元素按上述規(guī)則輸出
private static void leftRightWay(int[] arr){
int len = arr.length;
int[] right = new int[len];
int[] left = new int[len];
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < len; i++) {
while(!stack.empty() && arr[i] < arr[stack.peek()]) {
int tempTop = stack.pop();
left[tempTop] = stack.empty() ? -1 : stack.peek();
right[tempTop] = i;
}
stack.push(i);
}
while(!stack.empty()) {
int tempTop = stack.pop();
left[tempTop] = stack.empty() ? -1 : stack.peek();
right[tempTop] = -1;
}
for(int i = 0; i < len; i++) {
System.out.println(left[i] + " " + right[i]);
}
}
復(fù)雜度
- 時(shí)間復(fù)雜度：O(N)姚建，每個(gè)元素被處理兩次矫俺，其索引入棧和出棧。
739. 每日溫度
方法一：動態(tài)規(guī)劃掸冤，詳解可去鏈接里查看
public int[] dailyTemperatures(int[] T) {
int len = T.length;
int[] result = new int[len];
result[len - 1] = 0;
for(int i = len - 2; i >= 0; i--) {
for(int j = i + 1; j < len; j += result[j]) {
// 重點(diǎn)在 j += result[j] 上
// 當(dāng)天溫度小于后一天溫度厘托，那么直接得出結(jié)果 1
// 當(dāng)天溫度大于后一天溫度，那么就得比較 [比后一天溫度還要高的那一天]稿湿，循環(huán)這個(gè)過程铅匹。
// 如果后一天溫度的后面沒有比它大的了，那自然也不可能比當(dāng)天溫度大了
if (T[i] < T[j]) {
result[i] = j - i;
break;
} else if (result[j] == 0) {
result[i] = 0;
break;
}
}
}
return result;
}
方法二：單調(diào)棧
算法
維護(hù)一個(gè)單調(diào)遞減的棧即可饺藤，棧內(nèi)存放的是元素索引
- 遍歷數(shù)組
- 如果當(dāng)前元素小于棧頂元素包斑，則入棧
- 否則，將棧頂元素出棧涕俗，
當(dāng)前元素索引 - 棧頂元素就是對應(yīng)位置的結(jié)果
public int[] dailyTemperatures(int[] T) {
int len = T.length;
int[] result = new int[len];
Stack<Integer> stack = new Stack();
for(int i = 0; i < len; i++) {
while(!stack.empty() && T[i] > T[stack.peek()]) {
int tempTop = stack.pop();
result[tempTop] = i - tempTop;
}
stack.push(i);
}
while(!stack.empty()) {
result[stack.pop()] = 0;
}
return result;
}
