东营区建设局网站,泡泡网,大连网站快速排名,网站如何做搜索功能的废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【单调栈的应用】#xff0c;使用【栈】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为喊一句号子鼓励自己程序员永不失业程序员走向架构本篇Blog的主题是【单调栈的应用】使用【栈】这个基本的数据结构来实现这个高频题的站点是CodeTop筛选条件为目标公司最近一年出现频率排序由高到低的去牛客TOP101去找只有两个地方都出现过才做这道题CodeTop本身汇聚了LeetCode的来源确保刷的题都是高频要面试考的题。
明确目标题后附上题目链接后期可以依据解题思路反复快速练习题目按照题干的基本数据结构分类且每个分类的第一篇必定是对基础数据结构的介绍。
每日温度【MID】
每日温度是单调栈的典型应用题
题干 解题思路
构造递减栈寻找右侧第一个大于当前元素的数遍历整个数组如果栈不空且当前数字大于栈顶元素满足结算条件所以需要取出栈顶元素进行结算由于当前数字大于栈顶元素的数字而且一定是第一个大于栈顶元素的数直接求出下标差就是二者的距离。继续看新的栈顶元素直到当前数字小于等于栈顶元素停止然后将数字入栈这样就可以一直保持递减栈且每个数字和第一个大于它的数的距离也可以算出来
初始化result的长度与原数组长度相同如果后续无结果录入则自动补0
代码实现
给出代码实现基本档案 基本数据结构栈 辅助数据结构无 算法无 技巧单调栈 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param n int整型 the n* return int整型*/public int[] dailyTemperatures(int[] temperatures) {// 1 入参判断如果数组为空则结果集为空数组if (temperatures null || temperatures.length 0) {return new int[temperatures.length];}// 2 定义单调递减栈单调栈存储当前温度下标和返回结果集StackInteger singleStack new StackInteger();int[] result new int[temperatures.length];// 3 遍历数组进行温度结算for (int i 0; i temperatures.length; i) {// 如果满足结算条件进行结算while (!singleStack.isEmpty() temperatures[i] temperatures[singleStack.peek()]) {// 1 弹出并记录当前温度记录时间int cur singleStack.pop();// 2 计算更大温度时间与当前温度时间差result[cur] i - cur;}// 结算完毕后元素入栈singleStack.push(i);}return result;}}复杂度分析
时间复杂度O(n)虽然 while 循环里套了一个 while 循环但是考虑到每个元素最多访问两次入栈一次和出栈一次所以时间复杂度是 O(n)。
空间复杂度O(n)O(n)。栈的空间
接雨水【HARD】
千呼万唤始出来经典题目接雨水使用单调栈来解决
题干
计算蓝色雨水部分的单位数量
解题思路
原题解地址单调栈就是保持栈内元素有序。和单调队列一样需要我们自己维持顺序没有现成的容器可以用。通常是一维数组要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置此时我们就要想到可以用单调栈了。
1 问题的求解方向
而接雨水这道题目我们正需要寻找一个元素右边最大元素以及左边最大元素来计算雨水面积首先单调栈是按照行方向来计算雨水
2 单调栈的单调顺序
从大到小还是从小到大呢从栈头元素从栈头弹出到栈底的顺序应该是从小到大的顺序。因为一旦发现添加的柱子高度大于栈头元素了此时就出现凹槽了栈头元素就是凹槽底部的柱子栈头第二个元素就是凹槽左边的柱子而添加的元素就是凹槽右边的柱子
3 遇到相同高度的柱子怎么办
如果遇到相同的元素更新栈内下标就是将栈里元素旧下标弹出将新元素新下标加入栈中。例如 5 5 1 3 这种情况。如果添加第二个5的时候就应该将第一个5的下标弹出把第二个5添加到栈中。因为我们要求宽度的时候 如果遇到相同高度的柱子需要使用最右边的柱子来计算宽度 4 栈里存什么
使用单调栈也是通过 长 * 宽 来计算雨水面积的。长就是通过柱子的高度来计算宽是通过柱子之间的下标来计算那么栈里有没有必要存一个pairint, int类型的元素保存柱子的高度和下标呢。其实不用栈里就存放下标就行想要知道对应的高度通过height[stack.top()] 就知道弹出的下标对应的高度了
所以栈的定义如下
stackint st; // 存着下标计算的时候用下标对应的柱子高度5 算法流程
以下逻辑主要就是三种情况
情况一当前遍历的元素柱子高度小于栈顶元素的高度 height[i] height[st.top()]情况二当前遍历的元素柱子高度等于栈顶元素的高度 height[i] height[st.top()]情况三当前遍历的元素柱子高度大于栈顶元素的高度 height[i] height[st.top()] 先将下标0的柱子加入到栈中st.push(0);。 栈中存放我们遍历过的元素所以先将下标0加进来。
然后开始从下标1开始遍历所有的柱子for (int i 1; i height.size(); i)。如果当前遍历的元素柱子高度小于栈顶元素的高度就把这个元素加入栈中因为栈里本来就要保持从小到大的顺序从栈头到栈底。代码如下
if (height[i] height[st.top()]) st.push(i);如果当前遍历的元素柱子高度等于栈顶元素的高度要跟更新栈顶元素因为遇到相相同高度的柱子需要使用最右边的柱子来计算宽度。
if (height[i] height[st.top()]) { // 例如 5 5 1 7 这种情况st.pop();st.push(i);
}如果当前遍历的元素柱子高度大于栈顶元素的高度此时就出现凹槽了
取栈顶元素将栈顶元素弹出这个就是凹槽的底部也就是中间位置下标记为mid对应的高度为height[mid]就是图中的高度1。此时的栈顶元素st.top()就是凹槽的左边位置下标为st.top()对应的高度为height[st.top()]就是图中的高度2。当前遍历的元素i就是凹槽右边的位置下标为i对应的高度为height[i]就是图中的高度3。
此时应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的元素三个元素来接水
雨水高度是 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度代码为int h min(height[st.top()], height[i]) - height[mid];雨水宽度是 凹槽右边的下标 - 凹槽左边的下标 - 1因为只求中间宽度代码为int w i - st.top() - 1 ;当前凹槽雨水的体积就是h * w。
求当前凹槽雨水的体积代码如下
while (!st.empty() height[i] height[st.top()]) { // 注意这里是while持续更新栈顶元素int mid st.top();st.pop();if (!st.empty()) {int h min(height[st.top()], height[i]) - height[mid];int w i - st.top() - 1; // 注意减一只求中间宽度sum h * w;}
}简化后的流程如下 继续结算5对应的雨水 4和6高度相同无需结算继续寻找高墙 寻找到高墙后继续结算
代码实现
给出代码实现基本档案 基本数据结构栈 辅助数据结构无 算法无 技巧单调栈 其中数据结构、算法和技巧分别来自
10 个数据结构数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树10 个算法递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法技巧双指针、滑动窗口、中心扩散
当然包括但不限于以上
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** max water* param arr int整型一维数组 the array* return long长整型*/public long maxWater (int[] arr) {// 1 入参判断数组为空结算0个单位雨水if (arr null || arr.length 0) {return 0;}// 2 定义单调栈存储元素下标,定义总的雨水单位StackInteger singleStack new StackInteger();int result 0;// 3 遍历数组进行雨水计算for (int i 0; i arr.length; i) {// 右边的墙大于当前栈顶元素满足结算条件进行结算while (!singleStack.isEmpty() arr[i] arr[singleStack.peek()]) {// 1 当前栈顶元素出栈int bottom singleStack.pop();// 如果当前栈顶只有一个元素弹出后栈空则无需结算因为左边界没有墙无法蓄水if (singleStack.isEmpty()) {break;}// 2 bottom已弹出此时的栈顶元素为左边墙,当前元素为右边界int left singleStack.peek();int right i;// 3 分别计算高度和宽度int height Math.min(arr[left], arr[i]) - arr[bottom];int weight i - left - 1;// 4 结算雨水单位并累加result height * weight;}// 结算完毕后继续存储单调递减元素singleStack.push(i);}return result;}
}复杂度分析
时间复杂度O(n)虽然 while 循环里套了一个 while 循环但是考虑到每个元素最多访问两次入栈一次和出栈一次所以时间复杂度是 O(n)。
空间复杂度O(n)O(n)。栈的空间
拓展知识普通栈与单调栈
普通栈和单调栈都是数据结构用于在计算机编程中处理和解决各种问题。它们的主要区别在于它们的行为方式和用途。 普通栈Regular Stack 普通栈是一种基本的数据结构遵循后进先出Last-In-First-OutLIFO的原则。这意味着最后放入栈的元素将首先被弹出。普通栈通常用于存储和管理临时数据如函数调用的上下文信息、表达式求值、括号匹配等。普通栈的操作包括压栈push和弹栈pop以及查看栈顶元素top。 单调栈Monotonic Stack 单调栈是一种特殊类型的栈它通常用于解决一类特定问题其中需要维护一个特定的单调性。单调栈分为单调递增栈和单调递减栈两种类型。单调递增栈栈内元素保持递增的顺序新元素入栈时会弹出比它小的元素。单调递减栈栈内元素保持递减的顺序新元素入栈时会弹出比它大的元素。单调栈常用于解决一些与查找元素位置或计算区间最大/最小值相关的问题如寻找下一个更大元素、寻找下一个更小元素、计算柱状图中每个柱子的最大矩形面积等问题。
单调栈的主要思想是利用栈来维护特定的单调性以快速查找和处理与这种单调性相关的问题。普通栈则是一种通用的数据结构没有特定的单调性要求用途更广泛。
