算法学习——LeetCode力扣单调栈篇

算法学习——LeetCode力扣单调栈篇

在这里插入图片描述

739. 每日温度

739. 每日温度 - 力扣（LeetCode）

描述

给定一个整数数组 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 <= 105
30 <= temperatures[i] <= 100

代码解析

单调栈

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。

用temperatures = [73, 74, 75, 71, 71, 72, 76, 73]为例来逐步分析，输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

  • 首先先将第一个遍历元素加入单调栈
    在这里插入图片描述
  • 加入T[1] = 74，因为T[1] > T[0]，而我们要保持一个递增单调栈（从栈头到栈底），所以将T[0]弹出，T[1]加入，此时result数组可以记录了，result[0] = 1，即T[0]右面第一个比T[0]大的元素是T[1]。
    在这里插入图片描述
  • 加入T[2]，同理，T[1]弹出
    在这里插入图片描述
  • 加入T[3]，T[3] < T[2] （当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况），加T[3]加入单调栈。
    在这里插入图片描述
  • 加入T[4]，T[4] == T[3] （当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况），此时依然要加入栈，不用计算距离，因为我们要求的是右面第一个大于本元素的位置，而不是大于等于！
    在这里插入图片描述
  • 加入T[5]，T[5] > T[4] （当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况），将T[4]弹出，同时计算距离，更新result

在这里插入图片描述

  • T[4]弹出之后， T[5] > T[3] （当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况），将T[3]继续弹出，同时计算距离，更新result

在这里插入图片描述
直到发现T[5]小于T[st.top()]，终止弹出，将T[5]加入单调栈
在这里插入图片描述
加入T[6]，同理，需要将栈里的T[5]，T[2]弹出
在这里插入图片描述

  • 同理，继续弹出
    在这里插入图片描述
  • 此时栈里只剩下了T[6]
    在这里插入图片描述
  • 加入T[7]， T[7] < T[6] 直接入栈，这就是最后的情况，result数组也更新完了。
  • 在这里插入图片描述

那result[6] , result[7]怎么没更新啊，元素也一直在栈里。

其实定义result数组的时候，就应该直接初始化为0，如果result没有更新，说明这个元素右面没有更大的了，也就是为0。

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> result(temperatures.size(),0);
        stack<int> st;

        st.push(0);

        for(int i=1 ; i<temperatures.size(); i++)
        {
            while( st.empty()==0  &&  temperatures[i] > temperatures[st.top()] )
            {
                result[st.top()] = i - st.top();
                st.pop();
            }
            st.push(i);
        }
        return result;
    }
};

496. 下一个更大元素 I

496. 下一个更大元素 I - 力扣（LeetCode）

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 <= 1000
0 <= nums1[i], nums2[i] <= 104
nums1和nums2中所有整数 互不相同
nums1 中的所有整数同样出现在 nums2 中

代码解析

和 739 完全一样

  • 739是找每一个点的右边第一个大于点
  • 该题是找部分点（num1）的右边第一个最大点

具体步骤

  • 用map记录num1出现的点
  • 然后和739一样找每一个右边第一个最大值
  • 找到后判断该点是否是num1里面的，是就保存，不是就放弃
  • 此处和739不同，739找到就保存
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result(nums1.size(),-1);
        stack<int> st;
        unordered_map<int,int> umap;
        for(int i=0 ; i<nums1.size(); i++)
        {
            umap[nums1[i]] = i; 
        }

        // for(auto it:umap) cout<<it.first<<' '<<it.second<<endl;

        st.push(0);
        for(int i=1 ;i<nums2.size();i++)
        {
            while(st.empty()==0 && nums2[i] > nums2[st.top()])
            {
                if(umap.count(nums2[st.top()]) > 0 )
                {
                    int index = umap[nums2[st.top()]];
                    result[index] = nums2[i];
                }
                st.pop();
            }
            
            st.push(i);
           
        }

        return result;
    }
};

503. 下一个更大元素 II

503. 下一个更大元素 II - 力扣（LeetCode）

描述

给定一个循环数组 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

代码解析

和496 类似，为循环数组。将num数组扩充两倍连起来即可

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> result(nums.size(),-1);
        vector<int> my_nums(nums.begin() , nums.end());
        stack<int> st;
        int indnx;

        // for(auto it:nums) my_nums.push_back(it); //循环插入
        my_nums.insert(my_nums.end(), nums.begin(), nums.end()); //insert插入
        st.push(0);
      
        for(int i=1 ; i<my_nums.size() ;i++)
        {
            while(st.empty()==0 && my_nums[i] > my_nums[st.top()])
            {	
            	//检测是否是第二圈
                if(st.top()>=nums.size()) indnx = st.top() - nums.size();
                else indnx = st.top();
                result[indnx] = my_nums[i];
                st.pop();
            }
            st.push(i);
        }
        return result;

    }
};

42. 接雨水

42. 接雨水 - 力扣（LeetCode）

描述

给定 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.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

代码解析

单调栈

在这里插入图片描述
从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。

因为一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。
在这里插入图片描述
遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。

例如 5 5 1 3 这种情况。如果添加第二个5的时候就应该将第一个5的下标弹出，把第二个5添加到栈中。

因为我们要求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度。
在这里插入图片描述

单调栈处理逻辑

  • 先将下标0的柱子加入到栈中

  • 然后开始从下标1开始遍历所有的柱子

  • 如果当前遍历的元素（柱子）高度小于栈顶元素的高度，就把这个元素加入栈中，因为栈里本来就要保持从小到大的顺序（从栈头到栈底）。

  • 如果当前遍历的元素（柱子）高度等于栈顶元素的高度，要跟更新栈顶元素，因为遇到相相同高度的柱子，需要使用最右边的柱子来计算宽度。

  • 如果当前遍历的元素（柱子）高度大于栈顶元素的高度，此时就出现凹槽了，如图所示：栈顶和栈顶的下一个元素以及要入栈的三个元素来接水！

  • 在这里插入图片描述

class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size()<=2) return 0;
        stack<int> st;
        int result = 0;
        st.push(0);

        for(int i=1 ; i<height.size() ;i++)
        {
        	//当前柱子比栈顶的小
            if(height[i] < height[st.top()])
                st.push(i);
            //当前柱子和栈顶相等
            else if(height[i] == height[st.top()])
            {
                st.pop();
                st.push(i);
            //当前柱子比栈顶的大，产生了凹陷
            }else if(height[i] > height[st.top()])
            {
                while(st.empty()==0 && height[i] > height[st.top()])
                {
                    int mid = st.top();
                    st.pop();
                    if(st.empty()==0) 
                    {
                        int left = st.top();
                        int right = i;
                        int h = min(height[left] , height[right]) - height[mid];
                        int w = right - left -1;
                        result += h*w;
                    }
                }
                st.push(i);
            }
        }
        return result;
    }
};

84. 柱状图中最大的矩形

84. 柱状图中最大的矩形 - 力扣（LeetCode）

描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例

示例 1:

在这里插入图片描述

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：

在这里插入图片描述

输入： heights = [2,4]
输出： 4

提示

1 <= heights.length <=105
0 <= heights[i] <= 104

代码解析

单调栈

我们可以遍历每根柱子，以当前柱子 i 的高度作为矩形的高，那么矩形的宽度边界即为向左找到第一个高度小于当前柱体 i 的柱体，向右找到第一个高度小于当前柱体 i 的柱体。

  • 和42接雨水类似
    为什么这么说呢，42. 接雨水 (opens new window)是找每个柱子左右两边第一个大于该柱子高度的柱子，而本题是找每个柱子左右两边第一个小于该柱子的柱子。

  • 那么因为本题是要找每个柱子左右两边第一个小于该柱子的柱子，所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序！
    在这里插入图片描述

  • 只有栈里从大到小的顺序，才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。

  • 所以本题单调栈的顺序正好与接雨水反过来。

  • 此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
      
        heights.insert(heights.begin(), 0); // 数组头部加入元素0
        heights.push_back(0); // 数组尾部加入元素
        stack<int> st;
        int result = 0;
        st.push(0);
        for(int i=1 ; i<heights.size() ;i++)
        {
            if( heights[i] > heights[st.top()] ) 
                st.push(i);
            else if(heights[i] == heights[st.top()])
            {
                st.pop();
                st.push(i);
            }
            else 
            {
                while(st.empty()==0 && heights[i] < heights[st.top()] )
                {
                    int mid = st.top();
                    st.pop();
                    if(st.empty()==0)
                    {
                        int left = st.top();
                        int right = i;
                        int sum = (right - left -1) * heights[mid];
                        cout<<left<<' '<<mid<<' '<<right<<' '<<sum<<endl;
                        if(sum > result) result = sum; 
                    }
                }
                st.push(i);   
            }
        }
        return result;
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/504015.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【带你了解动态规划】

【带你了解动态规划】

&#x1f525;博主&#xff1a;程序员不想YY啊&#x1f525; &#x1f4ab;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家&#x1f4ab; &#x1f917;点赞&#x1f388;收藏⭐再看&#x1f4ab;养成习惯 &#x1f308;希望本文对您有所裨益&#xff0c;如有…
阅读更多...
milvus knowhere源码编译测试

milvus knowhere源码编译测试

简介 Knowhere 是 Milvus 的核心向量执行引擎&#xff0c;集成了Faiss、Hnswlib和Annoy等多个向量相似度搜索库。 编译环境 操作系统: Ubuntu 22.04.4 gcc/g:11.4.0 cmake: 3.27.7 安装依赖 apt install build-essential libopenblas-dev libaio-dev python3-dev python…
阅读更多...
文生视频大模型Sora的复现经验

文生视频大模型Sora的复现经验

大家好&#xff0c;我是herosunly。985院校硕士毕业&#xff0c;现担任算法研究员一职&#xff0c;热衷于机器学习算法研究与应用。曾获得阿里云天池比赛第一名&#xff0c;CCF比赛第二名&#xff0c;科大讯飞比赛第三名。拥有多项发明专利。对机器学习和深度学习拥有自己独到的…
阅读更多...
win10怎么设置屏幕保护,win10设置屏幕保护方法

win10怎么设置屏幕保护,win10设置屏幕保护方法

电脑屏幕保护的作用主要有三个，第一，可以防止电脑因无人操作而使显示器长时间显示同一个画面，导致加速老化而缩短显示器寿命。第二，防止你离开电脑后屏幕上的隐私被偷窥。第三，大幅度降低屏幕亮度，有一定的省电作用。而Win10系统中呢是可以设置屏幕保护的，如果你想了解具…
阅读更多...
[flask]session的基本使用

[flask]session的基本使用

Cookie和Session的区别&#xff08;面试必备&#xff09;_cookie和session的作用和区别-CSDN博客 cooike和session都是用来跟踪浏览器用户身份的会话方式 ookie数据存放在客户的浏览器上&#xff0c;session数据放在服务器上 cooike相对于session来说的话&#xff0c;安全性没…
阅读更多...
【二分图】【二分图最大匹配】LCP 04. 覆盖

【二分图】【二分图最大匹配】LCP 04. 覆盖

作者推荐 视频算法专题 本文涉及知识点 二分图 二分图最大匹配 LeetCode LCP 04. 覆盖 你有一块棋盘&#xff0c;棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌&#xff0c;你想把这些骨牌不重叠地覆盖在完好的格子上&#xff0c;请找出你最多能在棋盘…
阅读更多...
Logback日志框架(超详细)

Logback日志框架(超详细)

logback-classic-1.2.3.jarhttp://链接: https://pan.baidu.com/s/1cA3gVB_6DEA-cSFJN6MDGw 提取码: sn8i 复制这段内容后打开百度网盘手机App&#xff0c;操作更方便哦 logback-core-1.2.3.jarhttp://链接: https://pan.baidu.com/s/19eCsvsO72a9PTqpXvXxrgg 提取码: 5yp…
阅读更多...
二维码门楼牌管理应用平台建设：引领现代化小区管理新篇章

二维码门楼牌管理应用平台建设：引领现代化小区管理新篇章

文章目录 前言一、二维码门楼牌管理应用平台概述二、三维动态单体化技术的优势三、二维码门楼牌管理应用平台的应用场景四、展望未来 前言 随着城市化的快速推进&#xff0c;现代化小区如雨后春笋般涌现&#xff0c;对小区管理的效率和智能化提出了更高要求。二维码门楼牌管理…
阅读更多...
代码随想录笔记|C++数据结构与算法学习笔记-动态规划(〇)|

代码随想录笔记|C++数据结构与算法学习笔记-动态规划(〇)|

本文是简单的视频总结&#xff1a;从此再也不怕动态规划了&#xff0c;动态规划解题方法论大曝光 &#xff01;详细信息还请看代码随想录讲解视频 文章目录 动态规划的常见类型动态规划的误区动规五步曲DP数组以及下标的含义递推公式DP数组如何初始化DP数组遍历顺序打印DP数组…
阅读更多...
WebViz可视化

WebViz可视化

WebViz可视化 Webviz是一个基于Web的可视化工具&#xff0c;意味着您可以通过浏览器/APP访问它&#xff0c;而不需要安装额外的软件。这对于远程访问和团队协作非常方便。 Foxglove是一个开源的工具包&#xff0c;包括线上和线下版。旨在简化机器人系统的开发和调试。它提供了…
阅读更多...
弧形导轨在自动化设备中的传动原理

弧形导轨在自动化设备中的传动原理

在自动化机械系统中&#xff0c;弧形导轨是一种常见的轨道结构&#xff0c;用于支撑和引导物体沿着指定的弧线运动。其工作原理基于几何学和物理学的原理。 弧形导轨通常由一个弧形的轨道和一个移动部件组成。轨道一般呈弧形&#xff0c;其几何形状可以是圆弧、椭圆弧等&#x…
阅读更多...
Java作业3-字符串

Java作业3-字符串

题目一 代码 import java.util.*; public class Main {public static void main(String[] args) {Scanner input new Scanner( System.in );String str input.nextLine();int len str.length();StringBuilder s new StringBuilder(len);//StringBuilder类参考菜鸟教程for…
阅读更多...
Unicode编码解码的全面介绍

Unicode编码解码的全面介绍

title: Unicode编码解码的全面介绍 date: 2024/3/30 18:30:48 updated: 2024/3/30 18:30:48 tags: Unicode起源编码演变UTF编码编码表详解编码解码实践Unicode挑战未来发展 1. Unicode的起源和发展 Unicode是一个国际标准&#xff0c;旨在统一世界上所有文字的表示方式。它最…
阅读更多...
Leetcode刷题记录面试基础题day1（备战秋招）

Leetcode刷题记录面试基础题day1（备战秋招）

hello&#xff0c;你好鸭&#xff0c;我是康康&#xff0c;很高兴你能来阅读&#xff0c;昵称是希望自己能不断精进&#xff0c;向着优秀程序员前行!&#x1f4aa;&#x1f4aa;&#x1f4aa; 目前博客主要更新Java系列、数据库、项目案例、计算机基础等知识点。感谢你的阅读和…
阅读更多...
redis学习-redis配置文件解读

redis学习-redis配置文件解读

目录 1.单位说明 2. include配置 3. network网络配置 3.1 bind绑定ip配置 3.2保护模式protected-mode配置 3.3端口号port配置​编辑 3.4超时断开连接timeout配置 4. general通用配置 4.1守护进程模式daemonize配置 4.2进程id存放文件pidfile配置 4.3日志级别loglevel配置 4.…
阅读更多...
音视频基础 （九）---FFmpeg过滤器框架

音视频基础 （九）---FFmpeg过滤器框架

ffmpeg的filter⽤起来是和Gstreamer的plugin是⼀样的概念&#xff0c;通过avfilter_link&#xff0c;将各个创建好的filter按 ⾃⼰想要的次序链接到⼀起&#xff0c;然后avfilter_graph_config之后&#xff0c;就可以正常使⽤。 ⽐较常⽤的滤镜有&#xff1a;scale、trim、over…
阅读更多...
Rabbit简单模式理解

Rabbit简单模式理解

简单模式 我们以最普通的方式去理解&#xff0c;并没有整合Springboot的那种 这是最简单的模式&#xff0c;一个生产者&#xff0c;一个消费者&#xff0c;一个队列 测试 1、 导包&#xff0c;没整合&#xff0c;不需要编写配置 2、需要生产者消费者 导包 <dependency…
阅读更多...
深度学习：基于PyTorch的模型解释工具Captum

深度学习：基于PyTorch的模型解释工具Captum

深度学习&#xff1a;基于PyTorch的模型解释工具Captum 引言简介示例安装解释模型的预测解释文本模型情绪分析问答 解释视觉模型特征分析特征消融鲁棒性 解释多模态模型 引言 当我们训练神经网络模型时&#xff0c;我们通常只关注模型的整体性能&#xff0c;例如准确率或损失函…
阅读更多...
cocos2.x =＞ node 属性修改

cocos2.x =＞ node 属性修改

简介 与节点属性相关的几个核心变量_trs、_matrix、_worldMatrix、_localMatDirty、_worldMatDirty。 _trs&#xff1a;存储节点的position、rotation、scale _matrix&#xff1a;存储节点的缩放、位移、旋转三者合一的变化矩陈&#xff08;仿射矩陈&#xff09; _worldMat…
阅读更多...
csp资料

csp资料

头文件 #include <bits/stdc.h> using namespace std isdigit(c); isalpha(c); switch(type){case value : 操作 } continue;//结束本轮循环 break;//结束所在的整个循环tips: //除法变乘法来算 //减法变加法 num1e42;//"1e4"表示10的4次方//用于移除容器中相…
阅读更多...
最新文章

Copyright @ 2022~2023