【四十八】【算法分析与设计】单调栈，单调栈模板，单调栈求个元素最近小于（等于）或者大于（等于）下标

求各个元素左边和右边的最近的小于（等于）的下标

最近的小于的计算过程:

实现的过程需要用到一个stack<==>st

黑盒:在st的元素都可以正确计算出最近小于的元素下标那么我们依次将arr中的元素入栈计即可

1.栈里面存储的是vector，vector存储的是元素的下标，同一个vector存储的这些下标对应的元素值是相同的

⒉栈从栈底到栈顶，vector对应的元素值是严格递增的，因为相同的值下标放到同一个vector里面了

3.当i下标想要入栈，必须保证i下标对应元素值大于等于栈顶vector对应的元素值或者栈空4.如果i下标对应元素值大于等于栈顶vector对应的元素值，直接入栈st.push({i))

5.如果i下标对应元素值小于栈顶vector对应的元素值，此时我们可以直到栈顶vector所有元素的左边最近小于元素下标和右边最近小于元素下标

6.左边最近小于元素下标是在栈顶下面压着的vector的最后一个元素7.右边最近小于元素下标是i

8.依次st.pop维护pop出来的vector里面所有元素最近最小下标，直到i下标对应元素值大于等于栈顶vector对应元素值，或者栈空

#include<bits/stdc++.h> // 包含C++标准库的所有头文件
using namespace std; // 使用标准命名空间std// 定义一个名为Solution的类
class Solution {
public:// 定义一个返回类型为vector<pair<int, int>>的成员函数getNearLessEqual，接收一个整数数组，表示获取最近的小于等于的元素下标vector<pair<int, int>> getNearLessEqual(vector<int>& arr) {vector<pair<int, int>> ret(arr.size()); // 创建一个大小与arr相同的pair数组，用于存储结果stack<int> st; // 定义一个整数栈for (int i = 0; i < arr.size(); i++) { // 遍历数组arr// 当栈不为空且当前元素小于等于栈顶元素对应的数组值时，进行循环while (!(st.empty() || arr[i] > arr[st.top()])) {int top = st.top(); st.pop(); // 取出栈顶元素并从栈中弹出int leftlessindex = st.empty() ? -1 : st.top(); // 如果栈为空，左侧最近小于等于元素的索引为-1，否则为栈顶元素索引ret[top].first = leftlessindex; // 设置结果中对应索引的第一元素ret[top].second = i; // 设置结果中对应索引的第二元素}st.push(i); // 将当前索引压入栈}// 清空栈，处理所有剩余元素while (!st.empty()) {int top = st.top(); st.pop();int leftlessindex = st.empty() ? -1 : st.top();ret[top].first = leftlessindex;ret[top].second = -1; // 由于右边没有更小的元素，所以设置为-1}return ret; // 返回结果}// 定义一个返回类型为vector<pair<int, int>>的成员函数getNearLess，功能与getNearLessEqual类似，但处理的是严格小于情况，获取最近的小于的元素下标vector<pair<int, int>> getNearLess(vector<int>& arr) {vector<pair<int, int>> ret(arr.size()); // 创建一个大小与arr相同的pair数组，用于存储结果stack<vector<int>> st; // 定义一个栈，栈中元素为整数vector，用于处理相等元素for (int i = 0; i < arr.size(); i++) { // 遍历数组arrwhile (!(st.empty() || arr[i] >= arr[st.top()[0]])) { // 当栈不为空且当前元素小于栈顶元素对应的数组值时，进行循环vector<int> top = st.top(); st.pop();int leftlessindex = st.empty() ? -1 : st.top().back(); // 如果栈为空，左侧最近小于元素的索引为-1，否则为栈顶元素的最后一个索引for (auto x : top) {ret[x].first = leftlessindex;ret[x].second = i;}}if (!st.empty() && arr[i] == arr[st.top()[0]]) { // 如果栈顶元素等于当前元素st.top().push_back(i); // 向栈顶元素的vector中添加当前索引} else {st.push({ i }); // 否则，将当前索引作为新vector压入栈}}// 清空栈，处理所有剩余元素while (!st.empty()) {vector<int> top = st.top(); st.pop();int leftlessindex = st.empty() ? -1 : st.top().back();for (auto x : top) {ret[x].first = leftlessindex;ret[x].second = -1; // 由于右边没有更小的元素，所以设置为-1}}return ret; // 返回结果}// 定义一个返回类型为vector<pair<int, int>>的成员函数getNearLess，获取最近的小于等于元素的下标的plus版本，这种版本可以快速改变为获取最近的小于的版本
vector<pair<int, int>> getNearLessEqual_1(vector<int>& arr) {vector<pair<int, int>> ret(arr.size()); // 创建一个大小与arr相同的pair数组，用于存储结果stack<vector<int>> st; // 定义一个栈，栈中元素为整数vectorfor (int i = 0; i < arr.size(); i++) { // 遍历数组arr// 当栈不为空且当前元素小于等于栈顶元素对应的数组值时，进行循环while (!(st.empty() || arr[i] > arr[st.top()[0]])) {vector<int> top = st.top(); st.pop(); // 取出栈顶元素并从栈中弹出int leftlessindex = st.empty() ? -1 : st.top().back(); // 如果栈为空，左侧最近小于等于元素的索引为-1，否则为栈顶元素的最后一个索引for (auto x : top) {ret[x].first = leftlessindex; // 设置结果中对应索引的第一元素ret[x].second = i; // 设置结果中对应索引的第二元素}}if (!st.empty() && arr[i] == arr[st.top()[0]]) { // 如果栈顶元素等于当前元素st.top().push_back(i); // 向栈顶元素的vector中添加当前索引} else {st.push({ i }); // 否则，将当前索引作为新vector压入栈}}// 清空栈，处理所有剩余元素while (!st.empty()) {vector<int> top = st.top(); st.pop();int leftlessindex = st.empty() ? -1 : st.top().back();for (auto x : top) {ret[x].first = leftlessindex;ret[x].second = -1; // 由于右边没有更小的元素，所以设置为-1}}return ret; // 返回结果}
};int main() {vector<int> arr = { 3,2,4,3,3,4,1,3,4,5 }; // 定义一个整数数组arr//以下是数组arr的索引：0 1 2 3 4 5 6 7 8 9vector<pair<int, int>> ret = Solution().getNearLess(arr); // 调用getNearLess函数，传递arr，并接收结果for (int i = 0; i < arr.size(); i++) {cout << i << ":" << "[" << ret[i].first << "," << ret[i].second << "]" << endl; // 打印每个元素的结果，显示左右侧最近的小于元素的索引}
}