首页 > 试题广场 >

单调栈

[编程题]单调栈
  • 热度指数:7324 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个长度为 n 的可能含有重复值的数组 nums,找到每一个位置 i 左边最近的位置 l 和右边最近的位置 r ,nums_lnums_r 比 nums_i 小。

请设计算法,返回一个二维数组,表示所有位置相应的信息。位置信息包括:两个数字 l 和 r。如果不存在,则值为 -1,下标从 0 开始。

数据范围: ,-10^9 \le nums_i \le 10^9
进阶:空间复杂度 ,时间复杂度

示例1

输入

[3,4,1,5,6,2,7]

输出

[[-1,2],[0,2],[-1,-1],[2,5],[3,5],[2,-1],[5,-1]]
示例2

输入

[1,1,1,1]

输出

[[-1,-1],[-1,-1],[-1,-1],[-1,-1]]

单调栈题意的基本题目

  • 找到比自己的小的左边加上右边的位置维护一个单调递增的栈,栈内元素从栈底到栈顶是单调递增

  • 分别用两次循环,一次寻找左边的一次寻找右边的位置索引

    import java.util.*;
    import  java.util.Stack;
    public class Solution {
      public int[][] foundMonotoneStack (int[] nums) {
                   int n=nums.length;
                   int [][]ans=new  int[n][2];
                   Stack<Integer> stack=new Stack<>();
                   for(int  i=0;i<n;i++){
                         while(!stack.isEmpty()&&nums[stack.peek()]>=nums[i])
                               stack.pop();
                              if(stack.isEmpty()){
                                   ans[i][0]=-1;
                              }
                              else{
                                    ans[i][0]=stack.peek();
                              }
    
                          stack.push(i);
                   }
               stack.clear();
            for(int  i=n-1;i>=0;i--){
                  while(!stack.isEmpty()&&nums[stack.peek()]>=nums[i])
                               stack.pop();
                              if(stack.isEmpty()){
                                   ans[i][1]=-1;
                              }
                              else{
                                    ans[i][1]=stack.peek();
                              }
    
                  stack.push(i);
            }
          return  ans;
      }
    }
发表于 2021-06-16 15:03:22 回复(1)
import java.util.*;


public class Solution {
    /**
     * 使用两次单调递增栈
     *
     * 
     * @param nums int一维数组 
     * @return int二维数组
     */
    public static int[][] foundMonotoneStack(int[] nums) {
        int[][] res = new int[nums.length][2];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            if (stack.isEmpty())
                res[i][0] = -1;
            else {
                res[i][0] = stack.peek();
            }
            stack.push(i);
        }
        stack.clear();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            if (stack.isEmpty())
                res[i][1] = -1;
            else {
                res[i][1] = stack.peek();
            }
            stack.push(i);
        }
        return res;
    }
}   

发表于 2021-11-23 15:20:34 回复(0)
保持栈底往栈顶是单调递增的,在弹栈时生成信息
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int一维数组 
     * @return int二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        int[][] res = new int[nums.length][2];
        for(int i = 0; i < nums.length; i++){
            res[i][0] = -1;
            res[i][1] = -1;
        }
        Stack<LinkedList<Integer>> stack = new Stack<>();     // 栈底往栈顶保持单调递增
        for(int i = 0; i < nums.length; i++){
            if(stack.isEmpty()){
                LinkedList<Integer> list = new LinkedList<>();
                list.add(i);
                stack.push(list);
            }else{
                if(nums[i] == nums[stack.peek().peekLast()]){
                    stack.peek().add(i);
                    continue;
                }else if(nums[i] < nums[stack.peek().peekLast()]){
                    while(!stack.isEmpty() && nums[i] < nums[stack.peek().peekLast()]){
                        // 单调性被破坏,开始弹栈生成信息
                        Iterator<Integer> list = stack.pop().iterator();
                        while(list.hasNext()){
                            int curIdx = list.next();
                            res[curIdx][1] = i;       // 栈顶每个元素右边比它小的都是nums[i]
                            // 栈顶每个元素左边比它小是下面压着的数,下面没有压那就是-1
                            if(!stack.isEmpty())
                                res[curIdx][0] = stack.peek().peekLast();
                            else
                                res[curIdx][0] = -1;
                        }
                    }
                }
                LinkedList<Integer> list = new LinkedList<>();
                list.add(i);
                stack.push(list);
            }
        }
        // 清算阶段,将栈中所有元素左边比它小的第一个数找到
        while(!stack.isEmpty()){
            Iterator<Integer> iter = stack.pop().iterator();
            while(iter.hasNext()){
                if(!stack.isEmpty())
                    res[iter.next()][0] = stack.peek().peekLast();
                else
                    res[iter.next()][0] = -1;
            }
        }
        return res;
    }
}

发表于 2021-11-19 11:59:52 回复(0)
#include <errno.h>
#include <stdbool.h>

#define OK 1
#define ERROR -1
#define MEMORY_OVERFLOW -2

#define NOT !

#define DEFAULT_CAPACITY 8
#define InitStack(S) __InitStack(S, DEFAULT_CAPACITY)

typedef int Status;

// ==================== 顺序栈数据结构表示与实现 ====================
typedef int SElemType;

typedef struct {
  SElemType* base;
  SElemType* top;
  size_t capacity;
} SqStack;

Status __InitStack(SqStack* S, int initialCapacity) {
  if (initialCapacity < 1) {
    printf("__InitStack ERROR: The initialCapacity %d Must be > 0!", initialCapacity);
    return ERROR;
  }
  if (!(S->base = (SElemType*) malloc(initialCapacity * sizeof(SElemType)))) {
    printf("__InitStack Memeory Overflow: %s\n", strerror(errno));
    exit(MEMORY_OVERFLOW);
  }
  S->top = S->base;
  S->capacity = initialCapacity;
  return OK;
}

bool StackEmpty(SqStack* S) {
  return S->top == S->base;
}

bool StackFull(SqStack* S) {
  return (S->top - S->base) == S->capacity;
}

size_t StackLength(SqStack* S) {
  return S->top - S->base;
}

void __large_capacity(SqStack* S) {
  if (!(S->base = (SElemType*) realloc(S->base, (S->capacity << 1) * sizeof(SElemType)))) {
    printf("__large_capacity Memeory Overflow: %s\n", strerror(errno));
    exit(MEMORY_OVERFLOW);
  }
  S->top = S->base + S->capacity;
  S->capacity <<= 1;
}

Status Push(SqStack* S, SElemType e) {
  if (StackFull(S))
    __large_capacity(S);
  *S->top++ = e;
  return OK;
}

Status Pop(SqStack* S, SElemType* ret) {
  if (StackEmpty(S)) {
    puts("Pop ERROR: The stack is empty!");
    return ERROR;
  }
  *ret = *--S->top;
  return OK;
}

SElemType GetTop(SqStack* S) {
  if (StackEmpty(S)) return -0x3F3F3F3F;
  return *((*S).top - 1);
}

Status DestroyStack(SqStack* S) {
  free(S->base);
  S->top = NULL;
  return OK;
}

// ==================== 顺序栈数据结构表示与实现 ====================

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param nums int一维数组 
 * @param numsLen int nums数组长度
 * @return int二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
int** foundMonotoneStack(int* nums, int numsLen, int* returnSize, int** returnColumnSizes) {
  
  SqStack S1, S2; // 创建两个单调递增栈
  InitStack(&S1);
  InitStack(&S2);
  
  int i, index;
  int ** ans = (int**) malloc(numsLen * sizeof(int*));
  *returnSize = numsLen;
  *returnColumnSizes = (int*) malloc(numsLen * sizeof(int));
  for (i = 0; i < numsLen; ++i) {
    *(ans + i) = (int*) malloc(2 * sizeof(int));
    memset(*(ans + i), -1, sizeof(*(ans + i)));
    (*returnColumnSizes)[i] = 2;
  }
  
  for (i = numsLen - 1; i >= 0; --i) {
    while (NOT StackEmpty(&S1) && *(nums + GetTop(&S1)) > *(nums + i)) {
      Pop(&S1, &index);
      *(*(ans + index)) = i;
    }
    Push(&S1, i);
  }
  
  for (i = 0; i < numsLen; ++i) {
    while (NOT StackEmpty(&S2) && *(nums + GetTop(&S2)) > *(nums + i)) {
      Pop(&S2, &index);
      *(*(ans + index) + 1) = i;
    }
    Push(&S2, i);
  }
  
  DestroyStack(&S1); DestroyStack(&S2);
  return ans;
}

发表于 2021-07-07 12:48:06 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int一维数组 
     * @return int二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        LinkedList<Integer>stk=new LinkedList<>();
        int[][]res=new int[nums.length][2];
        
        for(int i=0;i<nums.length;i++){
            while(!stk.isEmpty()&&nums[stk.peekLast()]>=nums[i]){
                res[stk.peekLast()][1]=i;
                stk.pollLast();
            }
            if(!stk.isEmpty()){
                res[i][0]=stk.peekLast();
            }else res[i][0]=-1;
            stk.addLast(i);
        }
        while(!stk.isEmpty()){
            res[stk.pollLast()][1]=-1;
        }
        return res;
    }
}

发表于 2021-06-28 13:49:08 回复(0)
class Solution:
    def foundMonotoneStack(self , nums ):
        # write code here
        n = len(nums)
        res = [[-1, -1] for _ in range(n)]
        stack = []
        for i in range(n):
            while stack and nums[stack[-1]] >= nums[i]:  # 保证stack里始终从下往上递增的
                stack.pop()
            if not stack:
                res[i][0] = -1
            else:
                res[i][0] = stack[-1]  # 这里stack的最上面比nums[i]小
            stack.append(i)  # 这里append的值肯定比pop的值要小,所以pop出来的值就没有用了
        stack.clear()
        for j in range(n - 1, -1, -1):  # 倒序
            while stack and nums[stack[-1]] >= nums[j]:  # 这里也是一样的逻辑,stack从下往上递增
                stack.pop()
            if not stack:
                res[j][1] = -1
            else:
                res[j][1] = stack[-1]
            stack.append(j)
        return res

发表于 2021-09-20 16:54:35 回复(0)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        // 定义一个数组 保存左边界的结果
        // 思路就是,从左向右开始计算,去计算每个值的左边界,存在记录,不存在就是-1
        vector<int> vec1;
        vec1.push_back(-1);
        int n = nums.size();
        for(int i=1; i<nums.size(); i++)
        {
            bool flag = false;
            for(int j=i-1; j>=0; j--)
            {
                if(nums[i] > nums[j])
                {
                    vec1.push_back(j);
                    flag = true;
                    break;
                }
            }
            if(!flag)
                vec1.push_back(-1);
        }
        // 定义一个右边界的数组,从右开始往左计算,计算每个值的有边界,存在记录,不存在-1
        // 另外顺序是是逆序的,所有需要reverse 其实也可以直接定义一个等大的数组 
        // 可以节约reverse的时间
        vector<int> vec2;
        vec2.push_back(-1);
        for(int i=n-2; i>=0; i--)
        {
            bool flag = false;
            for(int j=i+1; j<n; j++)
            {
                if(nums[i] > nums[j])
                {
                    vec2.push_back(j);
                    flag = true;
                    break;
                }
            }
            if(!flag)
                vec2.push_back(-1);
        }
        reverse(vec2.begin(), vec2.end());
        // 重新装成输出的格式
        vector<vector<int>> res;
        for(int i = 0; i<n; i++)
        {
            res.push_back({vec1[i], vec2[i]});
        }
        return res;
    }
};

发表于 2022-09-06 10:20:08 回复(0)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return intvector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        vector<vector<int>>ans(nums.size(),vector<int>(2));
        
        int stack[1000]={0};
        int top = 0;
        //left
        ans[0][0] = -1;
        stack[top++] = 0;
        for(int i = 1; i < nums.size(); i++)
        {
            while(top != 0){
                if(nums[i] > nums[stack[top-1]]){
                    ans[i][0] = stack[top-1];
                    stack[top++] = i;
                    break;
                }else{
                    top--;
                }
            }
            if(top == 0){
                stack[top++] = i;
                ans[i][0] = -1;
            }
        }
        
        //right
        ans[nums.size()-1][1] = -1;
        top=0;
        stack[top++] = nums.size()-1;
        for(int i = nums.size()-1; i >= 0; i--)
        {
            while(top != 0){
                if(nums[i] > nums[stack[top-1]]){
                    ans[i][1] = stack[top-1];
                    stack[top++] = i;
                    break;
                }else{
                    top--;
                }
            }
            if(top == 0){
                stack[top++] = i;
                ans[i][1] = -1;
            }
        }
        return ans;
        
    }
};

L值,第一个为-1,并将第一个元素下标进栈,对于后续每个元素ai,都与栈顶下标对应的的元素比较,如果栈顶下标元素小,则ai的L值为栈顶下标,并将ai下标进栈,否则,出栈继续比较直到有L值或者栈空,栈空则说明左边没有比ai小的元素,ai的L值为-1,ai下标进栈。

R值同理,从右往左遍历。


发表于 2021-01-19 00:52:44 回复(0)
双指针感觉也可以
class Solution:
    def foundMonotoneStack(self, nums: List[int]) -> List[List[int]]:
        # write code here

        res = []
        for i in range(len(nums)):
            l, r = i, i
            while l >= 0:
                if nums[i] <= nums[l]:
                    l -= 1
                else:
                    break

            while r < len(nums):
                if nums[i] <= nums[r]:
                    r += 1
                else:
                    break
            if r == len(nums):
                r = -1
            res.append([l, r])
        return res

编辑于 2024-03-15 23:27:36 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int一维数组 
     * @return int二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        int arr[][]=new int[nums.length][2];
        for(int i=0;i<nums.length;i++){
            int left=-1;
            int right=-1;
            //最左边
            if(i==0){
                //左
                arr[i][0]=-1;
                //右遍遍历寻找最近比arr[i]小的值
                for(int j=i+1;j<arr.length;j++){
                    if(nums[j]<nums[i]){
                        right=j;
                        break;
                    }
                }
                arr[i][1]=right;
                
            }
            //最右边
            if(i==nums.length-1){
                //右
                arr[i][1]=-1;
                //左遍历寻找最近比arr[i]小的值
                for(int j=i-1;j>=0;j--){
                    if(nums[j]<nums[i]){
                        left=j;
                        break;
                    }
                }
                arr[i][0]=left;
            }
            //中间情况
            if(i!=0&&i!=nums.length-1){
                //左遍历寻找最近比arr[i]小的值
                for(int j=i-1;j>=0;j--){
                    if(nums[j]<nums[i]){
                        left=j;
                        break;
                    }
                }
                arr[i][0]=left;
                //右遍历寻找最近比arr[i]小的值
                for(int j=i+1;j<nums.length;j++){
                    if(nums[j]<nums[i]){
                        right=j;
                        break;
                    }
                }
                arr[i][1]=right;
            }
        }
        return arr;
    }
}

发表于 2023-05-24 18:10:57 回复(0)

单调递增栈。遇到小的通通出栈。

import java.util.*;
public class Solution {
    public int[][] foundMonotoneStack (int[] nums) {
         List<Integer> leftList = new ArrayList<>();
         List<Integer> rightList = new ArrayList<>();
         int[][] res = new int[nums.length][2];
         for(int i = 0; i < res.length; ++i) {
            res[i][0] = -1;
            res[i][1] = -1;
         }
         for(int i = 0; i < nums.length; ++i) {
            while(leftList.size() != 0 && nums[leftList.get(leftList.size() - 1)] > nums[i]) {
                res[leftList.get(leftList.size() - 1)][1] = i;
                leftList.remove(leftList.size() - 1);
            }
            while(rightList.size() != 0 && nums[rightList.get(rightList.size() - 1)] > nums[nums.length - 1 - i]) {
                res[rightList.get(rightList.size() - 1)][0] = nums.length - 1 - i;
                rightList.remove(rightList.size() - 1);
            }
            rightList.add(nums.length - 1 - i);
            leftList.add(i);
         }
         return res;
    }
}
发表于 2023-05-09 14:32:22 回复(0)
package main

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param nums int一维数组 
 * @return int二维数组
*/
func foundMonotoneStack( nums []int ) [][]int {
    n:=len(nums)
    ans:=make([][]int,n)
    for i,_:=range ans{
        ans[i]=[]int{-1,-1}
    }
    stk1:=[]int{}
    stk2:=[]int{}
    for i,j:=0,n-1;i<n&&j>=0;i,j=i+1,j-1{
        for len(stk1)>0&&nums[stk1[len(stk1)-1]]>nums[i]{
            ans[stk1[len(stk1)-1]][1]=i
            stk1=stk1[:len(stk1)-1]
        }
        stk1=append(stk1,i)
        for len(stk2)>0&&nums[stk2[len(stk2)-1]]>nums[j]{
            ans[stk2[len(stk2)-1]][0]=j
            stk2=stk2[:len(stk2)-1]
        }
        stk2=append(stk2,j)
    }
    return ans
}

发表于 2023-03-09 00:47:35 回复(0)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        vector<vector<int>> res;
        for(int i = 0;i<nums.size();++i)
        {
            int L = -1;
            int R = -1;
            int val = nums[i];
            for(int j = i-1;j>=0;--j)
            {
                if(nums[j]<nums[i])
                {
                    L = j;
                    break;
                }
            }
            for(int z = i+1;z < nums.size();++z)
            {
                if(nums[z]<nums[i])
                {
                    R = z;
                    break;
                }
            }
            res.emplace_back(vector<int>{L,R});
        }
        return res;
    }
};

发表于 2022-09-15 12:16:24 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @return int整型二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        int[][] res = new int[nums.length][2];
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < nums.length; i++){
            while(!stack.isEmpty() && nums[stack.peek()] > nums[i]){
                int j = stack.pop();
                res[j][1] = i;
            }
            if(stack.isEmpty() || nums[stack.peek()] == nums[i]){
                res[i][0] = -1;
            }else{
                res[i][0] = stack.peek();
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            res[stack.pop()][1] = -1;
        }
        return res;
    }
}

发表于 2022-09-13 19:24:51 回复(0)
public class Solution {
    public int[][] foundMonotoneStack (int[] nums) {
    	//由于本体存在重复值,需要使用双向链表存放相同值
        Stack<LinkedList<Integer>> stack = new Stack<>();
        //存放结果的数组
        int result[][] = new int[nums.length][2];
        //依次遍历nums中每一个元素,i为数组的下标
        for(int i=0;i<nums.length;i++) {
        	//栈本身遵顼从小到大的单调原则,如果出现反例则陆续从栈中弹出元素直到符合原则
        	//弹出的元素即是需要处理的信息
        	while(!stack.isEmpty()&&nums[stack.peek().peekLast()]>nums[i]) {
        		//取出栈顶的链表,从尾部开始一次赋值
        		LinkedList<Integer> tmp = stack.pop();
        		while(!tmp.isEmpty()) {
        			int index = tmp.pollLast();
        			//如果弹出元素后栈为空则left值为-1.否则left的值为当前栈顶链表的尾元素的值
        			//right值为即将进入栈的元素,下标就是i
        			if(stack.isEmpty()) {
        				result[index][0]=-1;
        				result[index][1]=i;
        			}
        			else {
        				result[index][0]=stack.peek().peekLast();
            			result[index][1]=i;
        			}
        		}
        	}
        	//每遍历一个元素,相当于处理的是之前的元素,处理之后该元素仍需要入栈
        	//如果该元素的值和当前栈顶元素对应的值相等,则添加到一个链表中,否则创建一个新链表
        	if(!stack.isEmpty()&&nums[stack.peek().peekLast()]==nums[i]) {
        		stack.peek().addLast(i);
        	}
        	else {
        		LinkedList<Integer> res = new LinkedList<>();
        		res.addLast(i);
        		stack.add(res);
        	}
        }
        //此时所有的元素已经遍历完成,该添加进去的元素已经添加过了
        //此时栈里剩下的元素都是符合单调栈原则从小到大排列的
        //依次从栈顶弹出元素,right值为-1,left值为弹出后此时栈顶元素的链表尾部的下标
        //情况与上面类似,只不过right值为-1,当栈弹空时left为-1
        while(!stack.isEmpty()) {
        	LinkedList<Integer> tmp = stack.pop();
        	while(!tmp.isEmpty()) {
        		int index = tmp.pollLast();
        		if(stack.isEmpty()) {
        			result[index][0]=-1;
        			result[index][1]=-1;
        		}else {
        			result[index][0]=stack.peek().peekLast();
        			result[index][1]=-1;
        		}
        	}
        }
        return result;
    }
}
感觉写的挺清楚的,就是挺繁琐的,耗时有点高
发表于 2022-08-22 20:09:05 回复(1)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return intvector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        int top = -1;
        int n=nums.size();
        stack<int> stk;
        vector<vector<int>> array(n);//定义一个5*2的数组存放结果
        for (int i = 0; i < array.size(); i++)
              array[i].resize(2);
        for ( int i = 0; i < n; i++ ) 
        {
        while ( !stk.empty() && nums[stk.top()] >= nums[i] ) stk.pop();//保证栈顶元素是小于待入栈的
        if ( stk.empty() ) array[i][0] = -1;//栈为空,说明该位置元素左侧没有比它小的数
        else array[i][0] = stk.top();//如果栈不为空,则左侧比其值小的元素位置距离最近
        stk.push(i);//该元素入栈
        }
        while(!stk.empty()) stk.pop();//清空栈
        for ( int i = n - 1; i >= 0; i-- ) 
        {
        while (!stk.empty() && nums[stk.top()] >= nums[i] ) stk.pop();
        if ( stk.empty() ) array[i][1] = -1;//栈为空,说明该位置元素右侧没有比它小的数
        else array[i][1] = stk.top();//如果栈不为空,则右侧比其值小的元素位置距离最近
        stk.push(i);//该元素入栈
        }
        return array;
    }
};

发表于 2022-07-19 09:35:09 回复(0)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        int n = nums.size();
        vector<int> left(n) , right(n);
        stack<int> s;
        for(int i = 0;i < n;i++){
            while(!s.empty() && nums[i] <= nums[s.top()]) s.pop();
            left[i] = s.empty() ? -1 : s.top();
            s.push(i);
        }
        s = stack<int> ();
        for(int i = n - 1;i >= 0;i--){
            while(!s.empty() && nums[i] <= nums[s.top()]) s.pop();
            right[i] = s.empty() ? - 1 : s.top();
            s.push(i);
        }
        vector<vector<int>> res;
        for(int i = 0; i < n;i++) res.push_back({left[i],right[i]});
        return res;
    }
};

发表于 2022-07-10 21:12:53 回复(0)
//单调栈
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums intvector 
     * @return intvector<vector<>>
     */
    vector<vector<int> > foundMonotoneStack(vector<int>& nums) {
        // write code here
        stack<int> s;
        int n = nums.size();
        vector<vector<int>> res(n, vector<int>(2,0));
        for(int i = 0; i < n; ++i){
            while(!s.empty() && nums[s.top()] >= nums[i])
                s.pop();
            if(s.empty()) res[i][0] = -1;
            else res[i][0] = s.top();
            s.push(i);
        }
        while(!s.empty()) s.pop();
        for(int i = n-1; i >= 0; --i){
            while(!s.empty() && nums[s.top()] >= nums[i])
                s.pop();
            if(s.empty()) res[i][1] = -1;
            else res[i][1] = s.top();
            s.push(i);
        }
        return res;
    }
};


发表于 2022-04-26 21:10:10 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int一维数组 
     * @return int二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int[][] result = new int[nums.length][2];
        stack.push(-1);
        for(int i=0; i<nums.length; i++) {
            
            while(stack.peek()!=-1 && nums[stack.peek()]>nums[i]) {
                //因为比较的数字一定比栈顶元素小,所以这里可以设定每个栈顶元素的右边较小数
                result[stack.peek()][1] = i;
                stack.pop();
            }
            //上面while循环中条件必须是>,不能是>=,因为等于的情况不能把结果加入结果集,需要单独提出来讨论
            //(如果与栈顶元素相等说明自己左边的最近较小数与栈顶元素左边较小数一样,如果不相等说明栈顶元素就是左边的最近较小数)。
            if(stack.peek()!=-1 && nums[stack.peek()]==nums[i]) {
                result[i][0] = result[stack.peek()][0];
            }else {
                result[i][0] = stack.peek();
            }
            stack.push(i);
        }
        //stack中剩余的说明这些数字右边都没有比自己小的数字(因为是单调递增栈),那么把他们的结果集里第二个数字设为-1
        while(stack.peek()!=-1){
            result[stack.pop()][1] = -1;
        }
        return result;
    }
}

发表于 2022-04-04 17:56:42 回复(0)
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int一维数组 
     * @return int二维数组
     */
    public int[][] foundMonotoneStack (int[] nums) {
        Deque<Integer> stack = new LinkedList<>();
        stack.push(-1);
        int len = nums.length;
        int[][] res = new int[len][2];
        for(int i = 0; i < len; i++){
            while (stack.peek() != -1 && nums[stack.peek()] >= nums[i]){
                stack.poll();
            }
            res[i][0] = stack.peek();
            stack.push(i);
        }
        stack.clear();
        stack.push(-1);
        for(int i = len - 1; i >= 0; i--){
            while (stack.peek() != -1 && nums[stack.peek()] >= nums[i]){
                stack.poll();
            }
            res[i][1] = stack.peek();
            stack.push(i);
        }
        return res;
    }
}


发表于 2022-03-07 20:34:57 回复(0)