算法训练day63完结撒花单调栈739每日温度496下一个更大的元素503下一个更大的元素二

本文主要是介绍算法训练day63完结撒花单调栈739每日温度496下一个更大的元素503下一个更大的元素二,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

739每日温度

什么时候用单调栈

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

#include <iostream>
#include <vector>
#include <stack>class Solution {
public:std::vector<int> dailyTemperatures(std::vector<int>& temperatures) {std::vector<int> result(temperatures.size(), 0);std::stack<int> stk;if (!temperatures.empty()) {stk.push(0);}for (int i = 1; i < temperatures.size(); i++) {if (temperatures[i] <= temperatures[stk.top()]) stk.push(i);else {while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {result[stk.top()] = i - stk.top();stk.pop();}stk.push(i);}}return result;}
};int main() {Solution sol;std::vector<int> tem = {73,74,75,71,69,72,76,73};std::vector<int> res = sol.dailyTemperatures(tem);for (int i: res) {std::cout << i << " " ;}return 0;
}

单调栈里面的元素单调递增或单调递减

496下一个更大的元素

单调栈的本质是空间换时间。单调栈的作用就是存放遍历过的元素

递增就是求第一个比他大的元素的位置,递减就是求第一个比他小的元素的位置

将当前元素和栈口元素做比较 T[i] 和T[st.top()],再用一个result数组来记录reslult[st.top()]

#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>class Solution {
public:std::vector<int> nextGreaterElement(std::vector<int>& nums1, std::vector<int>& nums2) {std::unordered_map<int, int> umap;for (int i = 0; i < nums1.size();i ++) {umap[nums1[i]] = i;}std::vector<int> result(nums1.size(), -1);std::stack<int> stk;stk.push(0);for (int i = 1; i < nums2.size(); i++) {if (nums2[i] <= nums2[stk.top()]) {stk.push(i);}else {while (!stk.empty() && nums2[i] > nums2[stk.top()]) {if (umap.find(nums2[stk.top()]) != umap.end()) {result[umap[nums2[stk.top()]]] = nums2[i];}stk.pop();}stk.push(i);}}return result;}
};int main() {Solution sol;std::vector<int> nums1 = {2,4};std::vector<int> nums2 =  { 1,2,3,4};std::vector<int> res=  sol.nextGreaterElement(nums1, nums2);for (int i : res) {std::cout << i  << "," ;}return 0;}

503下一个更大的元素二

处理循环数组,可以不扩充nums,而是在遍历的过程中模拟走了两边nums。模拟遍历两边nums,注意一下都是用i % nums.size()来操作\

#include <iostream>
#include <vector>
#include <stack>class Solution {
public:std::vector<int> nextGreaterElements(std::vector<int>& nums) {std::stack<int> stk;std::vector<int> result(nums.size(), -1);stk.push(0);for (int i = 1 ; i < 2*nums.size(); i ++) {if (nums[i % nums.size()] <= nums[stk.top()]) {stk.push(i % nums.size());}else {while (!stk.empty() && nums[i % nums.size()] > nums[stk.top()]) {result[stk.top()] = nums[i % nums.size()];stk.pop();}stk.push(i % nums.size());}}return result;}
};int main() {Solution sol;std::vector<int> nums = {1,2,1};std::vector<int> res = sol.nextGreaterElements(nums);for (int i : res) {std::cout << i << " ";}return 0;
}

易错点为while (!stk.empty() && nums2[i] > nums2[stk.top()])容易忘记!stk.empty()

这篇关于算法训练day63完结撒花单调栈739每日温度496下一个更大的元素503下一个更大的元素二的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/894199

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定

CSS3中使用flex和grid实现等高元素布局的示例代码

《CSS3中使用flex和grid实现等高元素布局的示例代码》:本文主要介绍了使用CSS3中的Flexbox和Grid布局实现等高元素布局的方法,通过简单的两列实现、每行放置3列以及全部代码的展示,展示了这两种布局方式的实现细节和效果,详细内容请阅读本文,希望能对你有所帮助... 过往的实现方法是使用浮动加

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W