惠州 网站建设app开发上海网站建设浦东

当前位置： 首页 > news >正文

惠州 网站建设app开发,上海网站建设浦东,合肥大型网站制,产品展示的手机网站#x1f320;作者#xff1a;阿亮joy. #x1f386;专栏#xff1a;《数据结构与算法要啸着学》 #x1f387;座右铭#xff1a;每个优秀的人都有一段沉默的时光#xff0c;那段时光是付出了很多努力却得不到结果的日子#xff0c;我们把它叫做扎根 目录#x1f449;… 作者阿亮joy. 专栏《数据结构与算法要啸着学》 座右铭每个优秀的人都有一段沉默的时光那段时光是付出了很多努力却得不到结果的日子我们把它叫做扎根 目录滑动窗口的最大值单调队列的实现单调栈的实现数组无重复值版本的单调栈每日温度数组有重复值版本的单调栈指标A的最大值总结滑动窗口的最大值 给你一个整数数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回 滑动窗口中的最大值 。 这是一道可以使用单调队列的经典题。如果使用暴力方法的话就是遍历一遍的过程中每次从窗口中再找到最大的数值这样很明显是 O(k × N) 的算法。而使用单调队列来解这道题目时间复杂度是 O(N)。 那什么是单调队列呢单调队列是具有单调性的队列其里面存储的元素单增或者单减。单调队列需要保证的一个功能就是每次插入元素或者删除元素其队头的元素都是最大值或者最小值。为了实现这个功能我们需要用双端队列 deque 来做适配器。 为了说明单调队列的功能假设数组中的元素是 6 4 2 5 3。注一下过程假设队头数据是最大值队头数据是最小值同理。窗口的右边界往右移动则说明要插入新数据。如果新插入的数据比队尾的数据小则直接将数据从队尾插入而如果新插入的数据对队尾的数据大则需要将队尾数据弹出直至队尾数据大于新插入的数据或队列为空。窗口的左边界往右移动则说明可能要弹出队头数据。如果从窗口出来的数据就是队头数据则说明队头数据已过期需要将队头数据弹出而如果从窗口出来的数据不是队头数据则不需要弹出队头数据。 为什么单调队列就能够保证它里面存储的就是窗口内的最大值呢其实它是通过新加入的值是否会比前面的值大如果是就将前面的元素从尾部弹出。因为新加入的元素肯定比它们晚离开窗口而且值有比它们大所以只需要保留新加入元素就可以保证窗口内的最大值在队列中。 那如何估计单调队列解决滑动窗口最大值的时间复杂度呢数组中的每个元素最多进队列一次出队列一次没有多余的操作所以整体的时间复杂度为 O(N)每次操作的平均复杂度为 O(1)。 单调队列的实现 // MyQueue.h #pragma once #include deque #include iostream #include vector #include assert.h using namespace std;class MyQueue { public:// 因为范围是左必右开的,所以_left初始为-1,_right初始为0// [_left, _right)MyQueue(const vectorint arr): _arr(arr), _left(-1), _right(0){}void push(){// 数组中的元素都进入过单调队列中了if (_right _arr.size())return;// 加入新元素时,将队尾元素弹出至队列为空或队尾元素大于新加入的元素while (!_q.empty() _arr[_q.back()] _arr[_right]){_q.pop_back();}_q.push_back(_right);_right;}// _arr [_left, _right)void pop(){// 左边界大于等于右边界,说明窗口内没有数据了,// 直接返回即可if (_left _right - 1)return;// 因为_left初始值是-1,所以需要先加加_left_left;if (_q.front() _left){_q.pop_front();}}int front(){// 如果队列为空,直接断言报错assert(!_q.empty()); return _arr[_q.front()];}private:int _left; // 窗口的左边界int _right; // 窗口的右边界的再右一个位置dequeint _q; // 使用双端队列来实现单调队列,双端队列中存的是下标vectorint _arr; };MyQueue 类使用说明 申请一个滑动窗口对象时需要传入一个 vector 对象。上面的滑动窗口类可以自己手动控制滑动窗口的大小。使用一次 push 接口就表明滑动窗口的右边界向右移动而使用一次 pop 接口就表明滑动窗口的左边界向右移动。滑动窗口左右边界向右移动双端队列中存储的数据会是否需要弹出见上文讲解 知道如何使用 MyQueue 类后我们就可以轻松地解决最开始的题目了。 注需要将 MyQueue 类拷贝到 LeetCode 上 class Solution { public:vectorint maxSlidingWindow(vectorint nums, int k) {MyQueue q(nums);// 形成大小为k的窗口for(int i 0; i k; i){q.push();}vectorint ret;ret.push_back(q.front()); // 将当前窗口中的最大值尾插到ret中for(int i k; i nums.size(); i){// 左右边界同时向右移动一次即可保存滑动窗口的大小为kq.push();q.pop();ret.push_back(q.front()); // 记录滑动窗口的最大值}return ret;} };注单调队列的实现方式有很多需要根据具体的题目来定制相应的单调队列不能死板地认为单调队列只有一种实现方式。 单调栈的实现 单调栈也是具有单调性的栈其存储的元素是单增或者单剪。单调栈通常用于寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置。 给定数组 arr { 5 4 3 6 1 2 0 7 }请你求出数组中每个元素的左边和右边第一个比自己大的元素。暴力的方法来到 i 位置向左向右遍历找出第一个比 i 位置上元素大的元素。很明显这种方式的时间复杂度为 O(N^2)。 如果采用单调栈呢解决上面问题的时间复杂度为 O(N)。过程如下图 为什么上面的过程就能够求出每个元素左边和右边第一个比自己大的元素呢证明如下图 如果数组中有重复的元素那么栈中里面放的就不再是下标了而是存储下标的 list 或者 vector。当新加入的元素比栈顶元素大时那么就生成信息了。那如何生成呢新加入的元素就是第一个比栈顶元素大的元素栈顶元素下面压着的链表尾部的元素就是左边第一个比栈顶元素大的元素。如果新加入的元素和栈顶元素相等那么新加入元素的下标尾插到 list 或 vector 中。 单调栈的实现在这里我就不实现成一个类了而将其实现出一个函数。如果大家想将其实现成一个类可以参考下面的代码来实现。 数组无重复值版本的单调栈 vectorvectorint getNearBiggerNoRepeat1(const vectorint arr) {// ret[i][0]存的值是左边第一个比arr[i]大的值的下标// ret[i][1]存的值是右边第一个比arr[i]大的值的下标vectorvectorint ret(arr.size(), vectorint(2));stackint st;for (int i 0; i arr.size(); i){// arr[i]为新插入的元素while (!st.empty() arr[st.top()] arr[i]){int popIndex st.top();st.pop();// 如果左边没有比自己大的数,左边界的下标设置为-1int leftBiggerIndex st.empty() ? -1 : st.top();ret[popIndex][0] leftBiggerIndex;// 如果新插入元素比栈顶元素大,那么新插入元素就是// 右边第一个比栈顶元素大的元素ret[popIndex][1] i;}// 添加元素操作不要忘了st.push(i);}// 生成栈中元素的信息while (!st.empty()){int popIndex st.top();st.pop();// 如果左边没有比自己大的数,左边界的下标设置为-1int leftBiggerIndex st.empty() ? -1 : st.top();ret[popIndex][0] leftBiggerIndex;// 如果新插入元素比栈顶元素大,那么新插入元素就是// 右边第一个比栈顶元素大的元素ret[popIndex][1] -1;}return ret; }现在数组无重复值版本的单调栈就实现好了我们找到题目来验证一下写得对不对吧 每日温度 给定一个整数数组 temperatures 表示每天的温度返回一个数组 answer 其中 answer[i] 是指对于第 i 天下一个更高温度出现在几天后。如果气温在这之后都不会升高请在该位置用 0 来代替。 很明显每日温度这道题目就可以通过单调栈来解决。而且这道题目只要求求出右边第一个比自己大的值就行了并不需要求左边第一个比自己大的值。那么就把上面的实现的单调栈代码拷贝到 LeetCode 去再实现下面的代码就行了。 vectorvectorint getNearBiggerNoRepeat(const vectorint arr) {// ret[i][0]存的值是左边第一个比arr[i]大的值的下标// ret[i][1]存的值是右边第一个比arr[i]大的值的下标vectorvectorint ret(arr.size(), vectorint(2));stackint st;for (int i 0; i arr.size(); i){// arr[i]为新插入的元素while (!st.empty() arr[st.top()] arr[i]){int popIndex st.top();st.pop();// 如果左边没有比自己大的数,左边界的下标设置为-1int leftBiggerIndex st.empty() ? -1 : st.top();ret[popIndex][0] leftBiggerIndex;ret[popIndex][1] i;}// 添加元素操作不要忘了st.push(i);}// 生成栈中元素的信息while (!st.empty()){int popIndex st.top();st.pop();int leftBiggerIndex st.empty() ? -1 : st.top();ret[popIndex][0] leftBiggerIndex;ret[popIndex][1] -1;}return ret; }class Solution { public:vectorint dailyTemperatures(vectorint temperatures) {vectorvectorint info getNearBiggerNoRepeat(temperatures);vectorint ret(temperatures.size());for(size_t i 0; i temperatures.size(); i){// info[i][1] 等于 -1 表示 temperature[i] 右边没有比它更高的温度了// info[i][0] 不等于 -1 表示 temperature[i] 右边有比它更高的温度// 最近的一天是在 info[i][1] - i 天后if(info[i][1] ! -1)ret[i] info[i][1] - i;elseret[i] 0;}return ret;} };用我们上面实现的单调栈来解决这道题目简直就是杀鸡用牛刀。解决这道题目我们只需要实现单调栈的主要逻辑就行了如下方代码所示 class Solution { public:vectorint dailyTemperatures(vectorint temperatures) {vectorint ret(temperatures.size());stackint st;st.push(0); // 数组第一个元素先入栈for(int i 1; i temperatures.size(); i){// 栈顶元素比新加入元素temperatures[i]小// 就要生成栈顶元素的信息while(!st.empty() temperatures[st.top()] temperatures[i]){int popIndex st.top();st.pop();ret[popIndex] i - popIndex;}st.push(i);}// 循环结束,栈中的元素也要生成信息while(!st.empty()){int popIndex st.top();st.pop();ret[popIndex] 0;}return ret;} };数组有重复值版本的单调栈 vectorvectorint getNearBiggerRepeat(const vectorint arr) {// ret[i][0]存的值是左边第一个比arr[i]大的值的下标// ret[i][1]存的值是右边第一个比arr[i]大的值的下标vectorvectorint ret(arr.size(), vectorint(2));stackvectorint st;for (int i 0; i arr.size(); i){while (!st.empty() arr[st.top()[0]] arr[i]){vectorint popVector st.top();st.pop();int leftBiggerIndex st.empty() ? -1 : st.top()[st.top().size() - 1];for (int popIndex : popVector){ret[popIndex][0] leftBiggerIndex;ret[popIndex][1] i;}}// 添加操作if (!st.empty() arr[st.top()[0]] arr[i]){st.top().push_back(i);}else{vectorint v;v.push_back(i);st.push(v);}}while (!st.empty()){vectorint popVector st.top();st.pop();int leftBiggerIndex st.empty() ? -1 : st.top()[st.top().size() - 1];for (int popIndex : popVector){ret[popIndex][0] leftBiggerIndex;ret[popIndex][1] -1;}}return ret; }void Test() {vectorint arr { 2, 3, 2, 5,6,7,3,3,3,5,8 };vectorvectorint ret getNearBiggerRepeat(arr);for (int i 0; i ret.size(); i){cout ret[i][0] : ret[i][1] endl;} }指标A的最大值 数组中所有数都是正数数组中累加和与最小值的乘积 假设叫做指标 A。给定一个数组 请返回子数组中 指标 A 最大的值。 思路求出数组中每个元素作为最小值时的指标 A要使子数组的指标 A 最大那么就要使子数组的累加和最大。那怎么才能让子数组的累加和最大呢就是找到左边和右边第一个比自己小的元素这样就能让子数组的累加和最大了。很明显这就需要用到单调栈了。 class Solution { public:int max(vectorint arr){int max -1;stackint st;st.push(0);for (int i 1; i arr.size(); i){// 该单调栈栈底元素是最大的,栈底元素是最小的while (!st.empty() arr[st.top()] arr[i]){int popIndex st.top();st.pop();// 栈为空时,说明从0到i-1的数中arr[popIndex]是最小的// 栈不为空时,说明从st.top()1到i-1的数中arr[popIndex]是最小的int leftSmallerIndex !st.empty() ? st.top() 1 : 0;int sum 0;for (int j leftSmallerIndex; j i; j){sum arr[j];}max sum * arr[popIndex] max ? sum * arr[popIndex] : max;}st.push(i);}// 循环结束,栈中的元素右边全是比自己大的数while (!st.empty()){int popIndex st.top();st.pop();// 栈为空时,说明从0到i-1的数中arr[popIndex]是最小的// 栈不为空时,说明从st.top()1到i-1的数中arr[popIndex]是最小的int leftSmallerIndex !st.empty() ? st.top() 1 : 0;int sum 0;for (int j leftSmallerIndex; j arr.size(); j){sum arr[j];}max sum * arr[popIndex] max ? sum * arr[popIndex] : max;}return max;} };上面的代码还有可以优化的地方就是先把前缀和存到一个数组中需要累加和的时候直接取即可。 class Solution { public:int max(vectorint arr){int size arr.size();vectorint sum(size);sum[0] arr[0];// 求前缀和for(int i 1; i size; i){sum[i] sum[i - 1] arr[i];}int ret -1;stackint st;st.push(0);for(int i 1; i size; i){while(!st.empty() arr[st.top()] arr[i]){int popIndex st.top();st.pop();// 栈为空,说明popIndex左边没有比它小的数,累加和为sum[i-1]// 栈不为空,说明popIndex左边有比它小的数,累加和为sum[i-1] - sum[st.top()]int Sum st.empty() ? sum[i - 1] : (sum[i - 1] - sum[st.top()]);ret ret (Sum * arr[popIndex]) ? ret : (Sum * arr[popIndex]);}st.push(i);}while(!st.empty()){int popIndex st.top();st.pop();// 在栈中的元素,右边没有比它们小的元素了// 栈为空,说明popIndex左边没有比它小的数,累加和为sum[size-1]// 栈不为空,说明popIndex左边有比它小的数,累加和为sum[size-1] - sum[st.top()]int Sum st.empty() ? sum[size - 1] : (sum[size - 1] - sum[st.top()]);ret ret (Sum * arr[popIndex]) ? ret : (Sum * arr[popIndex]);}return ret;} };总结 本篇博客主要讲解了两个非常实用的数据结构单调队列和单调栈、用单调队列解决 LeetCode 中的滑动窗口最大值问题、用单调栈解决 LeetCode 中的每日问题和牛客网中的指标 A 的最大值问题等。那么以上就是本篇博客的全部内容了如果大家觉得有收获的话可以点个三连支持一下谢谢大家❣️