力扣每日一刷(2023.9.24)
739 每日温度
题目：
给定一个整数数组
temperatures，表示每天的温度，返回一个数组answer，其中answer[i]是指对于第i天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用0来代替。 示例 1: 输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0] 示例 2: 输入: temperatures = [30,40,50,60] 输出: [1,1,1,0] 示例 3: 输入: temperatures = [30,60,90] 输出: [1,1,0] 提示：
1 <= temperatures.length <= 10530 <= temperatures[i] <= 100
思路
本题其实可以使用暴力解法实现的， 但是力扣的时间复杂度分析的有问题， O(n2)的时间复杂度尽然过不了。
所以只能寻求更简洁的方法， 那就是通过空间换取时间(单调栈思路)
使用单调栈， 如果出现单调递减的情况， 那么就直接入栈， 如果是递增的 ，那么就符合要求。 因为我们栈内存储的是元素的索引。 所以按照题目要求， 可以将分为2种情况讨论
- 当前元素 > 栈顶元素
- 当前元素 <= 栈顶元素
因为栈内存储的是数组元素的下标索引。所以这里只需要一次for循环就可以实现，然后找出栈顶元素对应的满足要求的索引， 索引相减 即可得到我们需要的位次。
情况一：当前元素 <= 栈顶元素
- 如果当前元素 小于等于栈顶元素， 那么就直接将当前元素的索引入栈， 继续往后找 ， 找到满足条件的。
情况二：当前元素 > 栈顶元素
- 如果比较得到 当前元素大于栈顶元素 ，那么这个元素就是第一个大于栈顶元素的索引， 所以直接索引相减即可得到大于栈顶元素的位次。同时将栈顶元素出栈， 栈顶出栈之后还需要对当前栈顶的元素再做判断， 万一当前栈顶的元素也满足条件呢？ 所以这里就需要使用循环来进行判断。 同时最后还需要将当前元素的索引入栈。
至于更细节的图解分析。 可以看卡哥的代码随想录学习(地址 : 代码随想录 (programmercarl.com))
实现
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int []res = new int[temperatures.length];
Stack<Integer> st = new Stack<>();
st.push(0); //先添加进入第一个元素的索引
for(int i =1 ; i < temperatures.length; i++){
//将当前元素的索引加入占 。然后再将比较与栈顶索引代表的元素的大小
if(temperatures[i] > temperatures[st.peek()]){
//需要考虑站内有多个元素的情况
while(!st.isEmpty() && temperatures[i] > temperatures[st.peek()]){
res[st.peek()] = i - st.pop(); //当前元素出栈
}
st.push(i);
}else {
// temperatures[i] <= temperatures[st.peek()]
st.push(i);
}
}
return res;
}
/*
暴力解法 ，超出时间限制
public int[] dailyTemperatures(int[] temperatures) {
int [] arr= new int[temperatures.length];
for(int i =0; i < temperatures.length;i++){
for(int j = i; j < temperatures.length ;j++){
if(temperatures[j] > temperatures[i]){
arr[i] = j - i;
break;
}
}
}
return arr;
}
*/
}496 下一个更大元素
题目：
nums1中数字x的 下一个更大元素 是指x在nums2中对应位置 右侧 的 第一个 比x大的元素。 给你两个 没有重复元素 的数组nums1和nums2，下标从 0 开始计数，其中nums1是nums2的子集。 对于每个0 <= i < nums1.length，找出满足nums1[i] == nums2[j]的下标j，并且在nums2确定nums2[j]的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是-1。 返回一个长度为nums1.length的数组ans作为答案，满足ans[i]是如上所述的 下一个更大元素 。 示例 1： 输入：nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出：[-1,3,-1] 解释：nums1 中每个值的下一个更大元素如下所述： - 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。 - 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。 - 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。 示例 2： 输入：nums1 = [2,4], nums2 = [1,2,3,4]. 输出：[3,-1] 解释：nums1 中每个值的下一个更大元素如下所述： - 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。 - 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。 提示：
1 <= nums1.length <= nums2.length <= 10000 <= nums1[i], nums2[i] <= 104nums1和nums2中所有整数 互不相同nums1中的所有整数同样出现在nums2中
进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？
思路
顺着题目要求写即可， 不用使用单调栈的方式， 因为使用暴力的方法时间复杂度可能更低
实现
暴力；
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int []res = new int[nums1.length];
for(int i =0 ;i < nums1.length; i++){
int j = 0;
//首先 先找到nums1[i] == nums2[j] 的j的下标。 然后本层索引才能从j开始
for(; j < nums2.length; j++){
if(nums1[i] == nums2[j]){
break;
}
}
for(; j< nums2.length; j++){
if(nums2[j] > nums1[i] ){
res[i] = nums2[j];
break;
}
}
if(j == nums2.length && res[i] == 0){
res[i] = -1;
}
}
return res;
}
}
503 下一个更大的元素
题目:
给定一个循环数组
nums（nums[nums.length - 1]的下一个元素是nums[0]），返回nums中每个元素的 下一个更大元素 。 数字x的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出-1。 示例 1: 输入: nums = [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2； 数字 2 找不到下一个更大的数； 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。 示例 2: 输入: nums = [1,2,3,4,3] 输出: [2,3,4,-1,4] 提示:
1 <= nums.length <= 104-109 <= nums[i] <= 109
思路
就是将nums再赋值一遍， 然后找是否有大于 当前栈顶元素的元素。如果有就添加到res数组中去。但是本题我们实现的时候是通过取余的方式， 这样可以减少遍历的次数。
其实没啥差别：
实现
class Solution {
public int[] nextGreaterElements(int[] nums) {
//边界判断
if(nums == null || nums.length <= 1) {
return new int[]{-1};
}
int size = nums.length;
int []nums1 = new int[2*size];
for(int i= 0 ;i < 2*size; i++){
if(i >= size){
nums1[i] = nums[i-size];
}else{
nums1[i] = nums[i];
}
}
int[] result = new int[2*size];//存放结果
Arrays.fill(result,-1);//默认全部初始化为-1
Stack<Integer> st= new Stack<>();//栈中存放的是nums中的元素下标
for(int i = 0; i < 2*size; i++) {
while(!st.empty() && nums1[i] > nums1[st.peek()]) {
result[st.peek()] = nums1[i];//更新result
st.pop();//弹出栈顶
}
st.push(i);
}
int []temp = new int[size];
for(int i=0 ; i< temp.length; i++){
temp[i] =result[i];
}
return temp;
}
} 优化之后的：
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);//默认全部初始化为-1
Stack<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];//更新result
st.pop();//弹出栈顶
}
st.push(i % size);
}
return result;
}
} 42 接雨水
题目：
给定
n个非负整数表示每个宽度为1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 示例 2： 输入：height = [4,2,0,3,2,5] 输出：9 提示：
n == height.length1 <= n <= 2 * 1040 <= height[i] <= 105
思路：
本题首先我实现的思路使用暴力解法 ，虽说是暴力， 但是复杂度却是和 使用单调栈相差无几的。
根据示例1 中的这张图
首先想到的是如何计算这个雨水的面积？ 横向还是纵向 ？
一个单位的雨水也就是相当于一个正方体的体积 ，我们要做的就是数正方体的个数 ，这里我们只需要考虑平面即可。同时因为横向的边长都是固定的1 ， 所以这里我们通过纵向来进行计算， 也就是按照列来计算。 算出每一列的有效雨水面积，然后累加即可得到整体的面积。
通过上述的描述， 我们知道了整体的思路 ，接下来就是具体的实现思路 。
- 循环遍历每个柱子，找出每个柱子最左边 和 最右边的边界（也就是左右两边第一个比当前柱子高的柱子）
- 这里需要注意的是， 我们第一个柱子 和 最后一个柱子是不能计算的，他们充当最后的边界
- 因为我们是按列进行累加的 ，同时每个柱子的宽度都是 1 ， 所以只需要算出列左右两边最短的列高 - 当前列高即可得到雨水的高。 也就可以得到雨水的体积。
实现：
上述步骤中的，第一步如果我们使用暴力解法的话， 也就是循环遍历每个柱子， 然后得到每个柱子的边界， 然后使用一个变量来接收 ，这样的作法虽然没错， 但是超时了 ，所以我们采用的是使用两个数组来接收每个柱子的边界，也同样单调栈的思路 : 通过空间换时间。 可以pass
class Solution {
public int trap(int[] height) {
//使用数组来记录每个节点的最大左右边界
int[] maxLeft = new int[height.length];
int[] maxRight = new int[height.length];
int sum =0 ;
//获取每柱子的最高左边界
maxLeft[0] = height[0];
for(int i =1; i<height.length;i++){
maxLeft[i] = Math.max(height[i], maxLeft[i-1]);
}
//获取每个柱子的最高右边界
maxRight[maxRight.length- 1] = height[height.length - 1];
for(int i = maxRight.length - 2 ; i>= 0; i--){
maxRight[i] = Math.max(height[i], maxRight[i+1]);
}
// 得到每个柱子容纳的水 ，然后添加
for(int i =0 ;i < height.length;i++){
sum += Math.min(maxRight[i], maxLeft[i]) - height[i];
}
return sum;
}
/**
双指针法， 最后超时
public int trap(int[] height) {
int sum =0 ;
for(int i =0 ; i< height.length;i++){
//定义左右边界
int lheight = height[i];
int rheight = height[i];
// 寻找左右边界
for(int j = i+1; j <height.length;j++){
rheight = Math.max(rheight,height[j]);
}
for(int j = i-1; j >=0 ; j--){
lheight = Math.max(lheight, height[j]);
}
//得到当前柱子能够容纳的雨水
int h = Math.min(lheight,rheight) - height[i];
if(h >0 ){
sum += h;
}
}
return sum;
}
*/
}单调栈实现
class Solution {
public int trap(int[] height) {
//使用单调栈实现
int sum = 0;
Stack<Integer> st = new Stack<>();
st.push(0); // 添加第一个索引
for(int i = 1;i < height.length; i++){
if(height[st.peek()] > height[i]){
st.push(i);
}
if(height[st.peek()] == height[i]){
//先弹出栈顶元素， 然后再入栈当前元素
st.pop();
st.push(i);
}else{
//如果栈顶的元素 < 当前元素 ，那么就需要弹出栈顶元素， 然后当前元素入栈
while(!st.isEmpty() && height[st.peek()] < height[i]){
int mid = st.peek();
st.pop();
if(!st.isEmpty()){
//之前的栈顶元素为柱子 。当前栈顶元素为它的左边界， 当前元素为它的右边界
int h = Math.min(height[i], height[st.peek()]) - height[mid];
int w = i - st.peek() - 1;
sum += h * w;
}
}
st.push(i);
}
}
return sum;
}
}84 柱形图中的最大矩形
题目:
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。 示例 1:
输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10 示例 2：
输入： heights = [2,4] 输出： 4 提示：
1 <= heights.length <=1050 <= heights[i] <= 104
思路
与上一题接雨水的 刚好相反，上题是找当前柱子的左右边界中的第一个大于 当前柱子的 。因为要接雨水，所以肯定要形成凹槽.。而本题则是找左右边界中第一个小于当前柱子高度的。 因为他要形成矩形 。所以找的就是小于当前柱子的。
所以实现思路还是和上道题是一样的，我们只需要在找边界的时候注意即可。
所以还是以空间换时间的好 ，单调栈虽然也是这个思路 ，但是所消耗的时间 和 空间都比使用数组大
实现
class Solution {
public int largestRectangleArea(int[] heights) {
//通过空间换时间的方法
int minLeft[] = new int[heights.length];
int minRight[] = new int[heights.length];
int sum = 0;
//找左边比当前元素小的
minLeft[0]= -1;
for(int i =1 ;i< heights.length;i++){
int t = i - 1;
//找到并且为每个元素赋值
while(t>= 0 && heights[t] >= heights[i]){
t = minLeft[t];
}
minLeft[i] = t;
}
//找到右两边第一个小于当前柱子的值
minRight[minRight.length - 1] = minRight.length ;
for(int i = minRight.length - 2; i>= 0 ;i--){
int t = i + 1;
while(t <= minRight.length-1 && heights[i] <= heights[t]){
t = minRight[t];
}
minRight[i] = t;
}
//计算得到每个柱子的最大面积
for(int i =0 ;i <heights.length; i++){
int weight = minRight[i] - minLeft[i] -1;
int height = heights[i];
sum = Math.max(sum, weight * height);
}
return sum;
}
/**
public int largestRectangleArea(int[] heights) {
//暴力解法
int sum = 0;
for(int i= 0 ;i <heights.length; i++){
//找到左右两边第一个小于当前柱子的值
int left = i;
int right = i;
for(; left >=0 ;left--){
if(heights[left] < heights[i] ) break;
}
for(; right < heights.length; right++){
if(heights[right] < heights[i]) break;
}
//算出当前柱子的宽度
int weight = right - left - 1;
int height = heights[i];
sum = Math.max(sum, weight * height);
}
return sum;
}
*/
}class Solution {
public int largestRectangleArea(int[] heights) {
// 数组扩容，在头和尾各加入一个元素
int [] newHeights = new int[heights.length + 2];
newHeights[0] = 0;
newHeights[newHeights.length - 1] = 0;
for (int index = 0; index < heights.length; index++){
newHeights[index + 1] = heights[index];
}
heights = newHeights;
int res = 0 ;
Stack<Integer> st = new Stack<>();
st.push(0);
for(int i =1; i < heights.length ;i++){
//如果栈顶元素 < 当前元素
if(heights[st.peek()] < heights[i]){
st.push(i);
}if(heights[i] == heights[st.peek()]){
st.pop();
st.push(i);
}else{
while(!st.isEmpty() && heights[st.peek()] > heights[i]){
int mid = st.pop(); //找到当前元素作为中间
if(!st.isEmpty()){
int left = st.peek();
int right = i;
int w = right - left - 1;
int h = heights[mid];
res = Math.max(res, w * h);
}
}
st.push(i);
}
}
return res;
}
}