代码随想录第46期 单调栈

这道题主要是单调栈的简单应用

class Solution {
public:vector<int> dailyTemperatures(vector<int>& T) {vector<int> result(T.size(),0);stack<int> st;st.push(0);for(int i=1;i<T.size();i++){if(T[i]<=T[st.top()]){st.push(i);}else{while(!st.empty()&&T[i]>T[st.top()]){result[st.top()]=i-st.top();st.pop();}st.push(i);}}return result;}
};

暴力模拟

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> result;for(int i=0;i<nums1.size();i++){int j=0;while(nums1[i]!=nums2[j]){j++;}while(j<nums2.size()&&nums1[i]>=nums2[j]){j++;}if(j>=nums2.size()){result.push_back(-1);}else{int val=nums2[j];result.push_back(val);}}return result;}
};

单调栈

class Solution {
public:vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {vector<int> result(nums1.size(),-1);stack<int> st;st.push(0);unordered_map<int, int> umap; // key:下标元素,value:下标for (int i = 0; i < nums1.size(); i++) {umap[nums1[i]] = i;}for(int i=1;i<nums2.size();i++){if(nums2[i]<=nums2[st.top()]){st.push(i);}else{while(!st.empty()&&nums2[i]>nums2[st.top()]){if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下标result[index] = nums2[i];}st.pop();}st.push(i);}}return result;}
};

比上一题多了个处理循环的操作

可以是模拟循环

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> result(nums.size(),-1);stack<int> st;st.push(0);for(int i=1;i<nums.size()*2;i++){if(nums[i%nums.size()]<=nums[st.top()]){st.push(i%nums.size());}else{while(!st.empty()&&nums[i%nums.size()]>nums[st.top()]){result[st.top()]=nums[i%nums.size()];st.pop();}st.push(i%nums.size());}}// 最后再把结果集即result数组resize到原数组大小result.resize(nums.size());return result;}
};

也可以是直接扩充数组

class Solution {
public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> nums1(nums.begin(), nums.end());nums.insert(nums.end(), nums1.begin(), nums1.end());vector<int> result(nums.size(),-1);stack<int> st;st.push(0);unordered_map<int,int> umap;for(int i=0;i<nums.size();i++){if(nums[i]<=nums[st.top()]){st.push(i);}else{while(!st.empty()&&nums[i]>nums[st.top()]){result[st.top()]=nums[i];umap[st.top()]=nums[i];st.pop();}st.push(i);}}// 最后再把结果集即result数组resize到原数组大小result.resize(nums.size() / 2);return result;}
};

这道题同样是一个双指针问题

class Solution {
public:int trap(vector<int>& nums) {
// max(min{左max,右max}-arr[i],0)
//预处理最大值  left:0-0最大值  0-1最大 0-i最大值
//          right:12-12最大值,11-12最大值 i-12最大值
/*int n=height.size();
int *lmax=new int[n];
int *rmax=new int[n];
lmax[0]=height[0];
for(int i=1;i<n;i++){
lmax[i]=max(lmax[i-1],height[i]);
}
rmax[n-1]=height[n-1];
for(int i=n-2;i>=0;i--){
rmax[i]=max(rmax[i+1],height[i]);
}
int ans=0;
for(int i=1;i<n-1;i++){ans+=max(0,min(lmax[i-1],rmax[i+1])-height[i]);
}return ans;*/
int l=0,r=nums.size()-1,lmax=nums[0],rmax=nums[nums.size()-1];
int ans=0;
while(l<=r){
if(lmax<=rmax){ans+=max(0,lmax-nums[l]);lmax=max(lmax,nums[l]);l++;
}else{ans+=max(0,rmax-nums[r]);rmax=max(rmax,nums[r]); r--;
}}
return ans;}};

与上一题类似,但是更麻烦些

双指针解法

class Solution {
public:int largestRectangleArea(vector<int>& heights) {vector<int> minLeftIndex(heights.size());vector<int> minRightIndex(heights.size());int size = heights.size();// 记录每个柱子 左边第一个小于该柱子的下标minLeftIndex[0] = -1; // 注意这里初始化,防止下面while死循环for (int i = 1; i < size; i++) {int t = i - 1;// 这里不是用if,而是不断向左寻找的过程while (t >= 0 && heights[t] >= heights[i]) t = minLeftIndex[t];minLeftIndex[i] = t;}// 记录每个柱子 右边第一个小于该柱子的下标minRightIndex[size - 1] = size; // 注意这里初始化,防止下面while死循环for (int i = size - 2; i >= 0; i--) {int t = i + 1;// 这里不是用if,而是不断向右寻找的过程while (t < size && heights[t] >= heights[i]) t = minRightIndex[t];minRightIndex[i] = t;}// 求和int result = 0;for (int i = 0; i < size; i++) {int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);result = max(sum, result);}return result;}
};

单调栈解法

class Solution {
public:int largestRectangleArea(vector<int>& heights) {int result = 0;stack<int> st;heights.insert(heights.begin(), 0); // 数组头部加入元素0heights.push_back(0); // 数组尾部加入元素0st.push(0);// 第一个元素已经入栈,从下标1开始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() && heights[i] < heights[st.top()]) { // 注意是whileint mid = st.top();st.pop();if (!st.empty()) {int left = st.top();int right = i;int w = right - left - 1;int h = heights[mid];result = max(result, w * h);}}st.push(i);}}return result;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Spring 中的 BeanDefinitionParserDelegate 和 NamespaceHandler

一、BeanDefinitionParserDelegate Spring在解析xml文件的时候&#xff0c;在遇到<bean>标签的时候&#xff0c;我们会使用BeanDefinitionParserDelegate对象类解析<bean>标签的内容&#xff0c;包括<bean>标签的多个属性&#xff0c;例如 id name class in…

ODC 如何精确呈现SQL耗时 | OceanBase 开发者工具解析

前言 在程序员或DBA的日常工作中&#xff0c;编写并执行SQL语句如同日常饮食中的一餐一饭&#xff0c;再寻常不过。然而&#xff0c;在使用命令行或黑屏客户端处理SQL时&#xff0c;常会遇到编写难、错误排查缓慢以及查询结果可读性不佳等难题&#xff0c;因此&#xff0c;图形…

Bugku CTF_Web——No one knows regex better than me

Bugku CTF_Web——No one knows regex better than me 进入靶场 一段PHP代码 <?php error_reporting(0); $zero$_REQUEST[zero]; $first$_REQUEST[first]; $second$zero.$first; if(preg_match_all("/Yeedo|wants|a|girl|friend|or|a|flag/i",$second)){$key$…

爬虫——JSON数据处理

第三节&#xff1a;JSON数据处理 在爬虫开发中&#xff0c;JSON&#xff08;JavaScript Object Notation&#xff09;是最常见的数据格式之一&#xff0c;特别是在从API或动态网页中抓取数据时。JSON格式因其结构简单、可读性强、易于与其他系统交互而广泛应用于前端与后端的数…

OpenHarmony-1.启动流程

OpenHarmony启动流程 1.OpenHarmony 标准系统启动引导流程 OpenHarmony标准系统默认支持以下几个镜像&#xff1a; 每个开发板都需要在存储器上划分好分区来存放上述镜像&#xff0c;SOC启动时都由bootloader来加载这些镜像&#xff0c;具体过程包括以下几个大的步骤&#xf…

力扣刷题日记之150.逆波兰表达式求值

今天继续给大家分享一道力扣的做题心得今天这道题目是 150.逆波兰表达式求值 题目如下&#xff0c;题目链接&#xff1a;https://leetcode.cn/problems/evaluate-reverse-polish-notation 1&#xff0c;题目分析 这道题说是一道中等难度的题目&#xff0c;其实如果理解了其中的…

Redis五大基本类型——String字符串命令详解(命令用法详解+思维导图详解)

目录 一、String字符串类型介绍 二、常见命令 1、SET 2、GET 3、MGET 4、MSET 使用MGET 和 使用多次GET的区别 5、DEL 6、SETNX SET、SET NX和SET XX执行流程 7、INCR 8、INCRBY 9、DECR 10、DECYBY 11、INCRBYFLOAT 12、APPEND 13、GETRANGE 14、SETRANGE …

如何知道表之间的关系(为了知识图谱的构建)

今天就简单点&#xff0c;把今天花时间做的一个程序说下。 我们在做常规知识图谱的时候&#xff0c;面临一个问题就是要知道关系是如何建立。如果表的数量比较少&#xff0c;人工来做还是比较容易的。 如果有非常多的表&#xff0c;并且这些表之间的关联关系都不清楚的情况下…

【软件测试】一个简单的自动化Java程序编写

文章目录 自动化自动化概念回归测试常见面试题 自动化测试金字塔 Web 自动化测试驱动 Selenium一个简单的自动化示例安装 selenium 库使⽤selenium编写代码 自动化 自动化概念 自动的代替人的行为完成操作。自动化在生活中处处可见 生活中的自动化可以减少人力的消耗&#x…

网络学习第四篇

引言&#xff1a; 我们在第三篇的时候出现了错误&#xff0c;我们要就行排错&#xff0c;那么我们要知道一下怎么配置静态路由实现ping通&#xff0c;这样子我们才知道下一跳到底是什么&#xff0c;为什么这样子做。 实验目的 理解和掌握静态路由的基本概念和配置方法。 实…

LeetCode题解:17.电话号码的数字组合【Python题解超详细,回溯法、多叉树】,知识拓展:深度优先搜索与广度优先搜索

题目描述 给定一个仅包含数字 2-9 的字符串&#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下&#xff08;与电话按键相同&#xff09;。注意 1 不对应任何字母。 示例 1&#xff1a; 输入&#xff1a;digits "23" 输出…

Python爬虫项目 | 一、网易云音乐热歌榜歌曲

文章目录 1.文章概要1.1 实现方法1.2 实现代码1.3 最终效果 2.具体讲解2.1 使用的Python库2.2 代码说明2.2.1 创建目录保存文件2.2.2 爬取网易云音乐热歌榜单歌曲 2.3 过程展示 3 总结 1.文章概要 学习Python爬虫知识&#xff0c;实现简单的一个小案例&#xff0c;网易云音乐热…

消息中间件分类

消息中间件&#xff08;Message Middleware&#xff09;是一种在分布式系统中实现跨平台、跨应用通信的软件架构。它基于消息传递机制&#xff0c;允许不同系统、不同编程语言的应用之间进行异步通信。 常见的消息中间件类型包括&#xff1a; 1. JMS&#xff08;Java Message S…

GoogleCloud服务器的SSH连接配置

首先&#xff0c;Google的服务器默认是通过自带的SSH网页端连接的&#xff0c;比较麻烦和容易断开&#xff0c;不是很好用&#xff0c;常见的解决办法有两种一种是通过修改ssh的配置&#xff0c;添加密码的方式进行连接&#xff0c;一种是通过配置公钥进行连接。 密码连接之前有…

31.3 XOR压缩和相关的prometheus源码解读

本节重点介绍 : xor 压缩value原理xor压缩过程讲解xor压缩prometheus源码解读xor 压缩效果 xor 压缩value原理 原理:时序数据库相邻点变化不大&#xff0c;采用异或压缩float64的前缀和后缀0个数 xor压缩过程讲解 第一个值使用原始点存储计算和前面的值的xor 如果XOR值为0&…

【图像压缩感知】论文阅读:Content-Aware Scalable Deep Compressed Sensing

tips&#xff1a; 本文为个人阅读论文的笔记&#xff0c;仅作为学习记录所用。本文参考另一篇论文阅读笔记 Title&#xff1a; Content-Aware Scalable Deep Compressed Sensing Journal&#xff1a; TIP 2022 代码链接&#xff1a; https://github.com/Guaishou74851/CASNet…

Neo4j Desktop 和 Neo4j Community Edition 区别

Neo4j Desktop 和 Neo4j Community Edition 的主要区别在于它们的用途、功能以及安装和管理方式。以下是这两者的详细对比&#xff1a; 1. Neo4j Desktop Neo4j Desktop 是一个图形化的桌面应用程序&#xff0c;主要为开发人员和个人使用提供了一个便捷的环境来安装、管理和运…

DAY120java审计第三方组件依赖库挖掘FastjsonShiroLog4jH2DB

组件漏洞判断插件 一、Tmall_demo-master&#xff08;fastjson&#xff09; 1、配置文件查找安装组件 1、JSON.parse(json) 2、JSON.parseObject 2、找可控的变量 3、利用组件漏洞 poc:propertyJson{"type":"java.net.Inet4Address","val":&q…

要查看你的系统是 x64(64位)还是 x86(32位),可以按照以下步骤操作

文章目录 1. 通过“系统信息”查看系统架构2. 通过“设置”查看系统架构3. 通过命令提示符查看系统架构4. 通过 PowerShell 查看系统架构5. 通过文件资源管理器查看系统架构总结 要查看你的系统是 x64&#xff08;64位&#xff09;还是 x86&#xff08;32位&#xff09;&…

通过JS删除当前域名中的全部COOKIE教程

有时候需要通过JS来控制一下网站的登录状态&#xff0c;就例如:网站登出功能&#xff0c;我们可以直接通过JS将所有COOKIE删除&#xff0c;COOKIE删除之后&#xff0c;网站自然也就退出了。 那么今天我就给大家分享一段JS的函数&#xff0c;通过调用这段函数就可以实现删除COO…