可以做英文纵横字谜的网站,蛋糕行业网站建设方案,网站建设找哪个平台,网站底部浮动代码单调栈 单调栈概念 每日温度 单调栈
概念
单调栈#xff08;Monotonic Stack#xff09;是一个特殊的数据结构#xff0c;它是一种栈#xff0c;但具有单调性的特性。单调栈有两种类型#xff1a;单调递增栈和单调递减栈。
在单调递增栈中#xff0c;栈内的元素保持递… 单调栈 单调栈概念 每日温度 单调栈
概念
单调栈Monotonic Stack是一个特殊的数据结构它是一种栈但具有单调性的特性。单调栈有两种类型单调递增栈和单调递减栈。
在单调递增栈中栈内的元素保持递增顺序即后入栈的元素总是大于或等于先入栈的元素。同样在单调递减栈中栈内的元素保持递减顺序即后入栈的元素总是小于或等于先入栈的元素。
以下是一个单调栈的基本实现以单调递减栈为例
def monotone_stack(nums): stack [] result [-1] * len(nums) for i in range(len(nums)): while stack and nums[i] nums[stack[-1]]: # 出栈并记录右边第一个比其小的元素的下标 result[stack.pop()] i stack.append(i) # 处理剩余栈内元素 while stack: result[stack.pop()] len(nums) return result这个函数会返回一个列表表示每个元素的右边第一个比其小的元素的下标。如果没有这样的元素则返回数组长度表示该元素右边没有其他元素。注意这个实现是针对单调递减栈的如果需要单调递增栈只需将比较符号从 改为 即可。
举个例子对于输入数组 [5, 3, 1, 4, 2]单调递减栈的输出为 [4, 2, 1, 5, -1]。这表示
数字 5 右边第一个比它小的数字是 4下标为 3数字 3 右边第一个比它小的数字是 2下标为 4数字 1 右边没有比它小的数字下标为 -1数字 4 右边第一个比它小的数字是 2下标为 4但实际上这个输出是不准确的因为数字 2 在数字 4 的左边。这里我们可以看到这个实现其实是在找右边第一个比其小的元素而不是左边。数字 2 右边没有比它小的数字下标为 -1
注意上述例子的输出描述有误。实际上对于输入数组 [5, 3, 1, 4, 2]正确的输出应该是每个元素的右边第一个比其大的元素的下标。为了得到左边第一个比其大的元素的下标我们需要稍微修改一下算法。
这是一个更准确的描述和示例展示如何使用单调栈找到每个元素左边第一个比其大的元素的位置
def monotone_stack(nums):stack []result [-1] * len(nums) # 初始化结果列表所有位置先设为-1for i in range(len(nums)):while stack and nums[i] nums[stack[-1]]:# 当前元素比栈顶元素大所以栈顶元素的左边第一个比它大的元素就是当前元素result[stack.pop()] istack.append(i) # 将当前元素下标入栈return result# 示例
nums [5, 3, 1, 4, 2]
print(monotone_stack(nums)) # 输出: [-1, 0, -1, 0, 3]在这个修正后的示例中
数字 5 左边没有比它大的数字下标为 -1数字 3 左边第一个比它大的数字是 5下标为 0数字 1 左边没有比它大的数字下标为 -1数字 4 左边第一个比它大的数字是 5下标为 0注意这里不是 3因为我们要找的是比 4 大的数字数字 2 左边第一个比它大的数字是 4下标为 3
这样我们就得到了每个元素左边第一个比其大的元素的位置。
每日温度
https://leetcode.cn/problems/daily-temperatures/description/?envTypestudy-plan-v2envIdtop-100-liked
public static int[] dailyTemperatures(int[] temperatures){ // 栈一直单调递减int n temperatures.length;int[] res new int[n];LinkedListInteger stack new LinkedList();for (int i temperatures.length - 1; i 0; i--) {int t temperatures[i];while (!stack.isEmpty() ttemperatures[stack.peek()]){// 有比之前大的数字就弹出去stack.pop();}if(!stack.isEmpty()){res[i] stack.peek()-i;}stack.push(i);}return res;}
