核心思想本质都是讲原本O ( n 2 ) O(n^2)O(n2)的算法优化为O ( n ) O(n)O(n)都是利用使用一个容器维护某段区间节省一段for循环同时这段区间维持单调性出发点删除容器内的冗余元素。理解都是删除冗余元素都是往容器末尾添加冗余元素从末尾取需要的元素。对于当前元素也要考虑到冗余元素单调栈例题830. 单调栈739. 每日温度相似题目⭐应用第1个小于/大于当前数的数暴力做法是两个for循环第一层循环表示当前数第二层循环用于搜索第一个小于当前数的数。使用容器存储第二个for循环中遍历的数意味着我们可以去掉一重for循环。方便查询目标数因此我们想到可以优化容器内的数据存储删除冗余的数据。删除容器中的冗余元素我们发现如果ij,且a[i]a[j]那么a[i]一定是当前容器中的冗余元素我们就可以删去它。此时容器末位的元素就是我们需要的第1个小于当前数的数。(如果容器为空则返回-1)然后按照这个规则容器内的元素就变成单调递增了然后我们用栈方便我们的实现。84.柱状图中最大的矩形intn,a;stackintst;voidsolve(){cinn;for(inti1;in;i){cina;while(!st.empty()st.top()a){st.pop();}if(st.empty())cout-1 ;else{coutst.top() ;}st.push(a);}}单调队列例题154. 滑动窗口⭐应用滑动窗口最大/最小值动态变换数组的最小和最大暴力方法遍历每一个窗口和窗口内元素尝试使用一个容器维护当前窗口这个容器需要实现窗口移动时容器大小减少以保持一致方便查询最大值或者最小值。因此我们想到可以优化容器内的数据存储删除冗余的数据。删除冗余数据对于最小值的情况ji,a[j]a[i]那么之后窗口a[i]一定不会被选中因此直接删除a[j]由此我们得到一个单调递增的数组。此时头部元素就是最小值。最后使用队列方便我们的实现。intn,k,a[1000009];dequeintq;voidsolve(){cinnk;for(inti1;in;i){cina[i];}// minfor(inti1;in;i){if(ik1){if(q.size()q.front()a[i-k]){q.pop_front();}}while(q.size()q.back()a[i]){q.pop_back();}q.push_back(a[i]);if(ik){coutq.front() ;}}coutendl;q.clear();// maxfor(inti1;in;i){if(ik1){if(q.size()q.front()a[i-k]){q.pop_front();}}while(q.size()q.back()a[i]){q.pop_back();}q.push_back(a[i]);if(ik){coutq.front() ;}}coutendl;}应用最小栈只是弹出元素的位置改变了classMinStack{private:stackintst;stackintst_min;public:MinStack(){}voidpush(intvalue){st.push(value);if(st_min.empty()||valuest_min.top()){st_min.push(value);}}voidpop(){if(st.top()st_min.top()){st_min.pop();}st.pop();}inttop(){returnst.top();}intgetMin(){returnst_min.top();}};/** * Your MinStack object will be instantiated and called as such: * MinStack* obj new MinStack(); * obj-push(value); * obj-pop(); * int param_3 obj-top(); * int param_4 obj-getMin(); */