Monotonic stack structure

The monotonic stack structure can obtain the elements larger than the elements at the left and right sides of a certain position in the array and the corresponding index values ;
For example, array Arr = [5,4,6,7,2]
Location 2 Corresponding elements 6; The larger element on the left is None, The larger element on the right is 7;

application 1

1. When there are no duplicate elements in the array , Returns the value of the first element on the left and right sides of each position in the array that is greater than the element of that position , If there is no element on one side that meets the condition , Just go back to -1

• Ideas
  Maintain a stack with absolute decrement of elements from the bottom of the stack to the top of the stack , Traverse the input elements in turn , When the decreasing stack condition is satisfied , Push elements onto the stack ; But if the traversed element does not satisfy the monotone stack condition , This is when the results are produced , At this time, the first element greater than on the left and right sides of the element index position at the top of the stack can be obtained ; The index of the element added to the top of the stack is k, that R_res[k]= At this time, the element to be pushed into the stack traversed ;L_res[k]= Elements in the stack k Bottom element
• code

#include<iostream>
#include<list>
#include<vector>
#include <stack>
using namespace std;

int main()
{
    
	stack<int> st;
	vector<int> R_res;
	vector<int> L_res;
	vector<int> in_vec = {
     3,6,4,2,8,9};
	R_res.resize(in_vec.size());
	L_res.resize(in_vec.size());

	for (int i = 0; i < in_vec.size(); i++)
	{
    
		while(!st.empty() && in_vec[st.top()] < in_vec[i])
		{
    
			int idx = st.top();
			R_res[idx] = in_vec[i];
			st.pop();
			if (!st.empty())
				L_res[idx] = in_vec[st.top()];
			else
				L_res[idx] = -1;
		}
		st.push(i);
	}
	
	int tail = -1;
	while (!st.empty())
	{
    
		int idx = st.top();
		R_res[idx] = tail;
		st.pop();
		if (!st.empty())
			L_res[idx] = in_vec[st.top()];
		else
			L_res[idx] = -1;
	}
	for (int i = 0; i < R_res.size(); i++)
	{
    
		cout << L_res[i] << " " << R_res[i] << endl;
	}
	return 0;
}

#output
-1 6
-1 8
6 8
4 8
-1 9
-1 -1

application 2

When there are duplicate elements in the array , Returns the value of the first element on the left and right sides of each position in the array that is greater than the element of that position

• Ideas
  The same is true for maintaining a monotone stack , Only the stack element is the address of the linked list , Put the index corresponding to the same element into an ordered or unordered table ;

• code

stack<vector<int>> st;

To be continued
video ： Two hours 30 Division

application 3

The array assumes the product of the cumulative sum and the minimum value , Suppose you have an index called an array A; So given a number , Please return the indicators in the subarray A Maximum value ;

Given array Arr = [5,3,2,1,6,4,7,8], Returns the maximum index in the subarray A;

• Ideas
  This array has no duplicate values , Relatively simple , The monotone stack can be used to solve the problem without repeating elements ; The set of all subarrays of an array can be divided into 8 A small collection ; It is a set of subarrays with each element as the minimum value ; So the problem becomes a subarray with each element of the array as the minimum value , indicators A Maximum ; For subarray sets with the same minimum value , The index corresponding to the largest subarray of cumulative sum of elements A The largest subarray ;
  So the problem is simplified to , Find the element index of each element whose left and right sides are smaller than this element , Then the elements in the left and right indexes are the indicators of this element A The largest subarray ; This uses the maximum stack ;
  Maintain a stack with increasing elements from the bottom of the stack to the top of the stack

• code

#include<iostream>
#include<list>
#include<vector>
#include <stack>
using namespace std;

int main()
{
    
	stack<int> st;
	vector<int> R_res;
	vector<int> L_res;
	int M = INT_MIN;
	vector<int> M_Arr;
	vector<int> in_vec = {
     3,6,4,2,8,9};
	R_res.resize(in_vec.size());// Index of records 
	L_res.resize(in_vec.size());// Index of records 

	for (int i = 0; i < in_vec.size(); i++)
	{
    
		while(!st.empty() && in_vec[st.top()] > in_vec[i])
		{
    
			int idx = st.top();
			R_res[idx] = i;
			st.pop();
			if (!st.empty())
				L_res[idx] = st.top();
			else
				L_res[idx] = -1;
		}
		st.push(i);
	}
	
	int tail = in_vec.size();
	while (!st.empty())
	{
    
		int idx = st.top();
		R_res[idx] = tail;
		st.pop();
		if (!st.empty())
			L_res[idx] = st.top();
		else
			L_res[idx] = -1;
	}
	for (int i = 0; i < R_res.size(); i++)
	{
    
		cout << L_res[i] << " " << R_res[i] << endl;
	}

	for (int i = 0; i < R_res.size(); i++)
	{
    
		int idx1 = L_res[i];
		int idx2 = R_res[i];
		int sum = 0;
		int res ;
		for (int k = idx1 + 1; k < idx2; k++)
			sum += in_vec[k];
		res = in_vec[i] * sum;
		M_Arr.push_back(res);
		M = max(M, res);
	}
	cout << "the max A is:" << M << endl;
	for (int i = 0; i < R_res.size(); i++)
		cout << M_Arr[i] << " ";
	return 0;
}

#output
-1 3
0 2
0 3
-1 6
3 6
4 6
the max A is:136
39 36 40 64 136 81