苏州安岭网站建设公司,做网站后期需要什么费用,英文网站建设优化,wordpress多域名绑定域名单调栈分为单调递增栈和单调递减栈#xff0c;通过使用单调栈我们可以访问到最近一个比它大#xff08;小#xff09;的元素。
#x1f34a; 单调递增栈#xff1a;单调递增栈就是从栈底到栈顶数据是依次递增#xff0c;通常是寻找某方向第一个比它小的元素。
#x1f…单调栈分为单调递增栈和单调递减栈通过使用单调栈我们可以访问到最近一个比它大小的元素。 单调递增栈单调递增栈就是从栈底到栈顶数据是依次递增通常是寻找某方向第一个比它小的元素。单调递减栈单调递减栈就是从栈底到栈顶数据是依次递减通常是寻找某方向第一个比它大的元素。适用场景 什么情况适合用单调栈来解决实际问题呢 通常是在数组中需要通过比较前后元素的大小关系来找最近的比它大小的元素问题时可以使用单调栈进行求解。
场景示例 1寻找左边第一个小于它的数
/*** 寻找左边第一个小于它的数* 单调递增栈单调递增栈就是从栈底到栈顶数据是依次递增通常是寻找某方向第一个比它小的元素* 单调递减栈单调递减栈就是从栈底到栈顶数据是依次递减通常是寻找某方向第一个比它大的元素** 题目描述 给定一个长度为 n ≤ 10 ^5 的数组 a输出每个数左边第一个比它小的数如果不存在则输出 − 1。** 在指针 i 从左往右遍历的过程中我们可以用一个栈来保存 i 左边的所有元素不包括i指向的元素* 下标越大的元素越接近栈顶下标越小的元素越接近栈底。* 每次我们访问栈顶只要栈顶元素大于等于 a [ i ]我们就将栈顶元素弹出直至栈顶元素小于 a [ i ] * 此时输出栈顶元素并将 a [ i ] 压入栈中。 由于栈中保存了 i 左边的所有元素所以只要有答案则答案一定在栈中。* 由于每个元素一定会被压入一次且至多弹出一次因此操作次数至多是2n故总时间复杂度为O(n)* param array* return*/public static int[] findFirstLeftLower(int[] array){DequeInteger linkList new LinkedList();int[] ans new int[array.length];for (int i 0; i array.length; i) {// 如果栈不为空且当前数小于等于栈顶元素则将栈顶出栈并通过linkList.push(array[i])将当前元素入栈while(!linkList.isEmpty() array[i] linkList.peek()){// 如果是求右边第一个大于它的数只需要替换成 array[i] linkList.peek()linkList.poll();}if(!linkList.isEmpty()){// 由于栈顶元素存放第一个比当前元素小的数则取出并给结果数组赋值ans[i] linkList.peek();}else{ans[i] -1;}linkList.push(array[i]);}/* for (int i 0; i ans.length; i) {System.out.print(ans[i] );}*/return ans;}2寻找左边第一个小于它的数的下标 /*** 寻找左边第一个小于它的数的下标* 单调递增栈单调递增栈就是从栈底到栈顶数据是依次递增通常是寻找某方向第一个比它小的元素* 单调递减栈单调递减栈就是从栈底到栈顶数据是依次递减通常是寻找某方向第一个比它大的元素** 题目描述 给定一个长度为 n ≤ 10 ^5 的数组 a输出每个数左边第一个比它小的数的下标如果不存在则输出 − 1。* 我们只需要注意几个点在当前条件下咱们栈中存的是下标而不是值* 所以需要修改两个地方* a[linkList.peek()] 而不是linkList.peek()* 不再是a[i]而是存储对应的下标i* param array* return*/public static int[] findFirstLeftLowerPosition(int[] array){DequeInteger linkList new LinkedList();int[] ans new int[array.length];for (int i 0; i array.length; i) {// 如果栈不为空且当前数小于等于栈顶元素则将栈顶出栈并通过linkList.push(array[i])将当前元素入栈while(!linkList.isEmpty() array[i] array[linkList.peek()]){// 如果是求右边第一个大于它的数的下标只需要替换成 array[i] linkList.peek()linkList.poll();}if(!linkList.isEmpty()){// 由于栈顶元素存放第一个比当前元素小的数 对应下标则取出并给结果数组赋值ans[i] linkList.peek();}else{ans[i] -1;}linkList.push(i);}/*for (int i 0; i ans.length; i) {System.out.print(ans[i] );}*/return ans;}3LeetCode 42. 接雨水 /*** LeetCode 42. 接雨水* 给定n个非负整数表示每个宽度为1的柱子的高度图计算按此排序的柱子下雨后能接多少雨水。* param height* return*/public static int trapWater(int[] height) {DequeInteger linkList new LinkedList();// 总雨水量int ans 0;int n height.length;for (int i 0; i n ; i) {// 当前柱子作为右柱子栈顶元素作为中间柱中间柱子前面作为左柱只能接左右两柱最低柱子高度的水while(!linkList.isEmpty() height[linkList.peek()] height[i]){// 右柱比栈顶更高才能接水。否则的话就是满足单调递减栈的那么我们继续入栈。int top linkList.pop();// 拿出前一个柱子if(linkList.isEmpty()){// 如果这根柱子后前面没有元素那就接不了雨水了因为接雨水的话至少需要左右两边都有柱子才行。break;}// 记录一下拿到的这根柱子的左边那根柱子的高度int left linkList.peek();// 根据柱状图推算宽度int currWidth i-left-1;int currHeight Math.min(height[left],height[i]) - height[top];ans currHeight*currWidth;}linkList.push(i);//经过上面一顿操作之后咱们的栈又满足单调性了于是将当前元素的下标入栈。}return ans;}参考资料 单调栈图文详解
