算法训练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

相关文章

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

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