且听疯吟

【算法】 mono stack

2022-11-20

mono stack

最近在练习题目的时候经常遇到mono stack的题目，总的来说题目还是非常非常的有意思，单调栈真心是个利器。可以解决非常多的复杂的问题。可以利用单调栈求出以当前值为最大值或者最小值的连续子数组的最大长度。

单调栈的原理

单调栈中的数据需要遵循两个原则：

  • 栈中的数据会是严格递增或者递减，则我们可以知道，假如单调栈中的数据为递减，则可以知道栈顶的数据一定为当前序列中最大的数据;假如单调栈中的数据为递增，则可以知道栈顶的数据一定为当前序列中最小的数据。一般情况下我们都会用dequeue来处理单调栈的数据，则可以知道队列的头部一定为当前序列中所求的最大值或者最小值。
  • 为了保持单调性，则每当加入一个新的元素时，则会将栈中所有比当前元素小或者大的数据全部进行出栈，则由此我们可以判断如下，假设当前的栈为递减：
    1
    从图中可以看出我们可以在$O(1)$的时间复杂度内求出当前序列的极值。栈中任意相邻的两个元素比如$(arr[i],arr[j])$,则表示所有处于$(i,j)$之间的元素均小于$arr[j]$,有了这个重要的推论，则许多问题都可以利用这个特性来求解，比如我们知道假设某个元素x大于$arr[j]$,则表示x一定大于所有位于$[i+1,j]$之间的元素。下面有几个非常有代表性的题目需要讨论下：
  1. 找到子数组长度为k的最大值
  2. Longest Sublist with Value Range Condition
  3. 子数组最小乘积的最大值
  4. 下一个更大元素 I
  5. 下一个更大元素 II

下一个更大元素 II

题目

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

地址

https://leetcode-cn.com/problems/next-greater-element-ii

题意

classical problem

思路

  1. 首先题目中要求循环处理，这个很简单我们只需要在数组后面对数组本身再进行重复复制一遍即可，这样我们即可完成循环处理。
  2. 最经典的处理莫过于如何求第一个比其小或者大的数的处理，我们利用单调栈，所有小于当前的数全部从栈中弹出，因为我们知道一个推论为，栈中任意相邻的两个元素比如$(arr[i],arr[j])$,则表示所有处于$(i,j)$之间的元素均小于$arr[j]$,此时我们即可利用单调性很快求出所有的值。

代码

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; ++i){
            nums.push_back(nums[i]);
        }
        vector<int> ans(n,-1);
        deque<int> dq;

        int j = 0;
        for(int i = 0; i < nums.size(); ++i){
            while(!dq.empty() && nums[dq.back()] < nums[i]){
                if(dq.back() < n){
                    ans[dq.back()] = nums[i];
                }
                dq.pop_back();
            }
            dq.push_back(i);
        }

        return ans;
    }
};

Longest Sublist with Value Range Condition

题目

Given a list of integers nums, return the length of the longest sublist where 2 * min(sublist) > max(sublist).

Constraints

n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [9, 1, 5, 5, 3, 3]
Output
4
Explanation
The sublist [5, 5, 3, 3] is the longest sublist that meet the criteria since 2 * 3 > 5.

地址

https://binarysearch.com/problems/Longest-Sublist-with-Value-Range-Condition

题意

双指针加单调栈

思路

  1. 这个题目更加经典，需要同时利用单调栈和双指针。

代码

int solve(vector<int>& nums) {
    int n = nums.size();
    int ans = 0;
    int j = 0;
    deque<int> minq;
    deque<int> maxq;
    
    for(int i = 0; i < n; ++i){
        // we remove all the element is more than nums[i]
        while(!minq.empty() && nums[minq.back()] > nums[i]) minq.pop_back();
        minq.push_back(i);
        // we remove all the element is less than nums[i]
        while(!maxq.empty() && nums[maxq.back()] < nums[i]) maxq.pop_back();
        maxq.push_back(i);
        while(!minq.empty() && !maxq.empty() && nums[maxq.front()] >= 2*nums[minq.front()]){
            while(!minq.empty() && minq.front() <= j) minq.pop_front();
            while(!maxq.empty() && maxq.front() <= j) maxq.pop_front();
            j++;
        }
        ans = max(ans,i-j+1);
    }

    return ans;
}

qiu

题目

Given a set of arrays of size and an integer , you have to find the maximum integer for each and every contiguous subarray of size for each of the given arrays.
nput Format

First line of input will contain the number of test cases T. For each test case, you will be given the size of array N and the size of subarray to be used K. This will be followed by the elements of the array Ai.

Constraints, where is the element in the array .

Output Format

For each of the contiguous subarrays of size of each array, you have to print the maximum integer.

Sample Input

2
5 2
3 4 6 3 4
7 4
3 4 5 8 1 4 10

Sample Output

4 6 6 4
8 8 8 10

地址

https://www.hackerrank.com/challenges/deque-stl/problem

题意

单调栈 + 滑动窗口

思路

  1. 这个题目更加经典，需要同时利用单调栈和双指针。利用单调性，单调栈中的栈头一定保存的是当前序列的最大值。同时利用滑动窗口，一旦窗口超过队头的元素，则将队头的元素进行删除即可。

代码

#include <iostream>
#include <deque> 
using namespace std;

void printKMax(int arr[], int n, int k){
	//Write your code here.
    deque<int> dq;
    int j = 0;
    
    for(int i = 0; i < n; ++i){
        while(!dq.empty() && arr[i] > arr[dq.back()]){
            dq.pop_back();
        }
        dq.push_back(i);
        while((i-j+1) > k){
            while(!dq.empty() && dq.front() <= j) dq.pop_front();
            j++;
        }
        if(i+1 >= k){
            cout<<arr[dq.front()]<<" ";
        }
    }
    cout<<endl;
    
    return;
}

int main(){
  
	int t;
	cin >> t;
	while(t>0) {
		int n,k;
    	cin >> n >> k;
    	int i;
    	int arr[n];
    	for(i=0;i<n;i++)
      		cin >> arr[i];
    	printKMax(arr, n, k);
    	t--;
  	}
  	return 0;
}

欢迎关注和打赏，感谢支持！

Tags: 算法
← 【kickstart】 kickstart 2021 roundD 【kickstart】 kick start 2021 roundB →

扫描二维码，分享此文章