单调栈
给出一个数组，求助每个位置上的数，左边比他小的和右边比他小的数，常规的方法时间复杂度是O(N^2)，利用单调栈结构可以用O(N)解决上述问题。
单调栈实现（无重复数）
设置一个栈，栈底到栈顶从小到大，按照顺序将数据压入栈中，如某个数压入时不满足此时的大小顺序要求，就需要将栈中的数弹出，此时记录这个数的左右情况，右边比这个数小的是当前准备压入的这个数，左边比他小的这个数是栈中当前数压着的那个。
当数组压完以后，栈中有剩余，则依次弹出，右边比当前数小的不存在，左边比当前数小的是栈中他压着的那个
代码实现
vector> getNearLessNum(vectorarr) { //创建结果数组，第一个位置存放左边小于他的索引，第二个位置存放右边小于这个数的索引 vector>res(arr.size(), vector(2, 0)); stackst; //将所有数依次尝试加入到栈中 for (int i = 0; i < arr.size(); i++) { //栈不为空，且栈顶元素大于当前元素，需要将栈顶元素弹出，此时找到了栈顶元素的左右小值 while (!st.empty() && arr[st.top()] > arr[i]) { int j = st.top(); st.pop(); int leftLessIndex = st.empty() ? -1 : st.top(); res[j][0] = leftLessIndex; res[j][1] = i; } st.push(i); } //全部数添加完毕以后，若栈不为空，弹栈，左边小于该数的是在栈中他压着的数，右边小于他的数不存在，即为-1 while (!st.empty()) { int j = st.top(); st.pop(); int leftLessIndex = st.empty() ? -1 : st.top(); res[j][0] = leftLessIndex; res[j][1] = -1; } return res;}
单调栈实现（有重复数）
将数组中的数的索引当做链表，放在栈中
若不满足整体顺序需要弹出时，右边的数就是使得它弹出的这个数，左边的数是栈中压着的那个数的索引链表末端的那个索引
同一个链表弹出来的左右关系应该是一致的
代码实现
vector> getNearLess(vectorarr) { vector>res(arr.size(), vector(2, 0)); stack>st; for (int i = 0; i < arr.size(); i++) { //栈不为空且栈顶的值大于当前值，此时记录左右结果，此时需要将栈顶的链表元素全部记录 while (!st.empty() && arr[st.top().front()] > arr[i]) { listpopIs = st.top(); st.pop(); int LeftLessIndex = st.empty() ? -1 : st.top().back(); for (int popI : popIs) { res[popI][0] = LeftLessIndex; res[popI][1] = i; } } //若当前值与栈顶元素相等，则将当前值添加到链表尾部 if (!st.empty() && arr[st.top().front()] == arr[i]) { st.top().push_back(i); }//如果栈为空或者当前数当于栈顶元素，则需要创建一个新的链表，然后将链表压入栈中。 else { list li; li.push_back(i); st.push(li); } } //所有元素都处理完以后，栈不为空，需要弹栈，左边的数是栈下面压着的链表的末结点，右边不存在即为-1 while (!st.empty()) { listpopIs = st.top(); st.pop(); int LeftLessIndex = st.empty() ? -1 : st.top().back(); for (int popi : popIs) { res[popi][0] = LeftLessIndex; res[popi][1] = -1; } } return res;}