代码随想录算法训练营第五十九天 | LeetCode 739. 每日温度、496. 下一个更大元素 I

news/2024/10/31 1:22:52/

代码随想录算法训练营第五十九天 | LeetCode 503. 下一个更大元素 II、42. 接雨水

文章链接:下一个更大元素 II、接雨水
视频链接:下一个更大元素 II、接雨水

1. LeetCode 503. 下一个更大元素 II

1.1 思路

  1. 本题是给一个数组求右边第一个比当前元素大的元素,好像和739. 每日温度差不多,但本题多了个循环数组的要求,首尾是相连的
  2. 思路 1:建立一个新数组,把原数组扩充一倍再放入这个新数组中,即这个新数组的长度是原数组的 2 倍,然后线性遍历求当前元素右边第一个比其大的元素,这样就不用循环数组了,最后返回一半数组即可。这么写就是空间复杂度就是创建了一个 2 倍的数组,时间复杂度就是 O(n)
  3. 思路 2:在原数组模拟循环的方式,通过取模的方式。遍历数组时还是通过 2 倍数组来遍历,for(int i=0;i<nums.length*2;i++),如果直接取 i,当超过 nums.length 时就会越界,因此 i=i%nums.length,这样当超出范围时一取模就又回来了。
  4. 单调栈的模板代码:result 数组存储结果,注意要将数组默认初始化为全-1 的值,因为本题找不到存的是-1,然后定义个栈,把 0 下标先放入 stack.push(0)。for(int i=1;i<nums.length*2;i++)从 1 开始是因为 0 下标已经存入。避免 i 越界,i=i%nums.length;if(nums[i]<=nums[stack.peek()])stack.push(i);else while(!stack.empty()&&nums[i]>nums[stack.peek()])result[stack.peek()]=nums[i],stack.pop();while 循环结束后 stack.push(i)。最终 return result。

1.2 代码

class Solution {public int[] nextGreaterElements(int[] nums) {//边界判断if(nums == null || nums.length <= 1) {return new int[]{-1};}int size = nums.length;int[] result = new int[size];//存放结果Arrays.fill(result,-1);//默认全部初始化为-1Stack<Integer> st= new Stack<>();//栈中存放的是nums中的元素下标for(int i = 0; i < 2*size; i++) {while(!st.empty() && nums[i % size] > nums[st.peek()]) {result[st.peek()] = nums[i % size];//更新resultst.pop();//弹出栈顶}st.push(i % size);}return result;}
}

2. LeetCode 42. 接雨水

2.1 思路

  1. 本题是给一个 height 数组“接雨水”,因为这些数组的元素形成柱子就会有一些凹槽,就能存些雨水,最后就返回能接多少岁雨水。
  2. 引出单调栈:单调栈适用于找到左边或者右边第一个比当前元素大的元素。本题的栈是递增还是递减呢?本题中我们不仅要求右边第一个比其大的元素,还要求左边第一个比其大的元素,因为要找到凹槽嘛,而我们确定一个凹槽就是要左右两边的柱子顶起来,中间有个底托起来
  3. 本题单调栈的工作过程是当前元素和栈顶元素比较,本题中如果当前元素大于栈顶元素那就是右边第一个比其大的元素,此时栈顶元素就是底了,右边的柱子也找到了,就差左边的柱子了,其实就在栈里,就是栈顶的下一个元素,这个就是左边第一个比其大的元素。
  4. 当前元素和栈顶元素的比较就大于等于小于三种情况。本题中,小于仍然是放入栈中;等于也是放入栈中,也可以把栈顶弹出再将但当前元素放入,其实都可以,但我们选择前者,这两个的区别就是计算有点差异而已;大于时,此时栈顶就是底,当前元素就是右边的柱子,左边的柱子就是栈顶下一个元素。
  5. 计算过程:底=stack.pop();柱子的高度要取最小值,因为取高的部分会漏出去,想象一下凹槽存水的原理木桶效应就知道了,h=Math.min(stack.peek(),height[i]),然后 h 减去 底的高度差就是存水的高度,凹槽的宽度就是右柱子的下标减去左柱子的下标,即 w=i-stack.peek()-1,为什么需要减 1,举例右柱子 4 下标,左柱子 2 下标,宽度应该是 1,求的就是中间凹槽的宽度,因此要-1。h*w 就是面积。因为栈顶前面弹出了,当前元素仍有可能比栈顶大,因此还能确定凹槽,因此用 while 循环遍历。前面说等于时是把当前元素直接放入还是先弹出再放入当前元素的时候,说的是都可以是因为,如果放入此时的最矮柱子和底的高度差是 0,面积也是 0,而如果弹出再放入就是少算了这个 0,因此没区别。
  6. 单调栈求面积是横向求的,而暴力是纵向求的。
  7. 代码实现:定义 sum 存面积,定义栈然后放入 0 下标,for(int i=1;i<height.length;i++)从 1 开始是因为 0 下标已经放入。if(height[i]<=height[stack.peek()])stack.push(i);else while(!stack.empty()&&heigth[i]>height[stack.peek()])int middle=stack.pop()这是底,if(!stack.empty())这里要判断一下不能为空栈,h=Math.min(height[stack.peek()],height[i])-height[mid] 这是高度差,w=i-stack.peek()-1 这是宽度;sum+=h*w。当 while 循环结束了也把当前元素放入栈中。最终 return sum。

2.2 代码

class Solution {public int trap(int[] height){int size = height.length;if (size <= 2) return 0;// in the stack, we push the index of array// using height[] to access the real heightStack<Integer> stack = new Stack<Integer>();stack.push(0);int sum = 0;for (int index = 1; index < size; index++){int stackTop = stack.peek();if (height[index] < height[stackTop]){stack.push(index);}else if (height[index] == height[stackTop]){// 因为相等的相邻墙,左边一个是不可能存放雨水的,所以pop左边的index, push当前的indexstack.pop();stack.push(index);}else{//pop up all lower valueint heightAtIdx = height[index];while (!stack.isEmpty() && (heightAtIdx > height[stackTop])){int mid = stack.pop();if (!stack.isEmpty()){int left = stack.peek();int h = Math.min(height[left], height[index]) - height[mid];int w = index - left - 1;int hold = h * w;if (hold > 0) sum += hold;stackTop = stack.peek();}}stack.push(index);}}return sum;}
}

http://www.ppmy.cn/news/1228967.html

相关文章

如何搞定电子画册制作,分分钟在线制作与宣传!

一提到公司宣传&#xff0c;大多数人会想到的是制作视频或纸质的小册子。随着互联网技术的发展&#xff0c;如今可以用电子画册来做宣传&#xff0c;不仅可以跨空间地域传播&#xff0c;并且仅需图文排版设计好&#xff0c;通过在线电子画册制作工具转换就能简单实现宣传&#…

ARTS 打卡第一周

ARTS AlgorithmReviewTipShare Algorithm 题目 class Solution {func mergeAlternately(_ word1: String, _ word2: String) -> String {var ans ""var idx1 word1.startIndexvar inx2 word2.startIndexwhile idx1 < word1.endIndex || idx2 < word2.e…

Java shp 转 GeoJson

文章目录 1. 依赖安装1.1 配置软件源1.2 引入依赖 2. 功能实现3. 参考链接 1. 依赖安装 1.1 配置软件源 在项目 pom.xml 添加, maven 的 settings.xml 配置的源&#xff0c;mirrorOf 不能是 *,不然安装不上 <project>...<repositories><repository><id…

第二部分:Module(也称为Package)

Module是一个传统的&#xff0c;较成熟的设计元数&#xff0c;虽然使用模块有一些技术上的原因&#xff0c;但主要原因确是“认知超载”。它为我们提供了两种观察模式&#xff0c;一是可以在module中查看细节&#xff0c;而不会被整个模型淹没&#xff0c;二是观察module之间的…

[Kettle] 公式

公式是用来计算数据流中数据的表达式 公式可以是"AB"这样的简单计算&#xff0c;也可以是类似"if/then"复杂业务逻辑判断的表达式 数据源 2019年11月月考成绩(Kettle数据集16).xlshttps://download.csdn.net/download/Hudas/88553816?spm1001.2014.300…

大白话解释什么类加载机制

大家好&#xff0c;我是伍六七。 今天我们来聊聊一个 Java 面试必考基础题目&#xff1a;类加载机制和双亲委派机制。 Java 类的加载机制是 Java 虚拟机&#xff08;JVM&#xff09;中类加载&#xff08;Class Loading&#xff09;和链接&#xff08;Linking&#xff09;的过…

pytest测试框架介绍(1)

又来每天进步一点点啦~~~ 一、Pytest介绍&#xff1a; pytest 是一个非常成熟的全功能的Python测试框架&#xff1b; pytest 简单、灵活、易上手&#xff1b; 支持参数化 能够支持简单的单元测试和复杂的功能测试&#xff0c;可以做接口自动化测试&#xff08;pytestrequests&…

穷举法、回溯法、分支界限法解决旅行商(TSP)问题

文章目录 一、问题描述二、穷举法解决2.1 介绍2.2 代码 三、回溯法解决四、分支界限法4.1 介绍4.2 代码 一、问题描述 有一个旅行商由某城市出发&#xff0c;经过所有给定的 n n n 个城市后&#xff0c;再回到出发的城市。除了出发的城市外&#xff0c;其它城市只经过一回。这…