讨论/求职面试/面试题|字节的一道面试题/
面试题|字节的一道面试题

前几天被问到一道字节的面试题:

input: 9,8,7,3,4,2,1
output: 9,8,7,2,1

input: 3,3,1
output: 1

找到数组中, 比左边所有数字都小, 比右边所有数字都大的 数字

先从左到右遍历,求一个leftMin数组,记录nums[i]左边的最小值;
再从右到左遍历求一个rightMax数组,记录nums[i]右边的最大值。
然后从左到右遍历每个元素,如果某元素满足leftMin[i]>nums[i]>rightMax[i],则求得该数

public class theByteDance {
    public static void main(String[] args) {
        int [] test = new int[]{3,3,1};

        System.out.println((find(test)));
    }


    public  static ArrayList<Integer> find(int[] arr){
        // 思路 找到左边的最大值, 找到右边的最小值, 然后判断自己是否 左 《 中 《 右

        ArrayList<Integer> res = new ArrayList<>();
        for(int i = 0; i < arr.length; i++) {
            int leftMin = Integer.MAX_VALUE;
            int rightMax = Integer.MIN_VALUE;
            //  左边
            for (int  j = 0; i > j; j++) {
                leftMin = Math.min(arr[j], leftMin);

            }
            //  右边

            for (int z =  arr.length - 1; z > i  ; z--){
                rightMax = Math.max(arr[z], rightMax);


            }
            if(leftMin > arr[i] && arr[i] > rightMax){

                res.add(arr[i]);

            }

        }
        return res;


    }
}

27
共 33 个回复

单调栈

13
该内容已被删除

维护一个单调递减栈,同时记录已遍历的最小值。遍历数组,对于数组当前值,小于最小值,则入栈,同时更新最小值;否则,出栈直到栈顶元素大于当前值。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Deque<Integer> stack = new LinkedList<>();
        int[] arr = new int[]{9,8,7,3,4,2,1};
        int minLeft = Integer.MAX_VALUE;
        for(int num: arr){
            if(num < minLeft){
                minLeft = num;
                stack.push(num);
            }else{
                while(!stack.isEmpty() && num >= stack.peek()){
                    stack.pop();
                }
            }
        }
        while(!stack.isEmpty()){
            System.out.println(stack.pop());
        }
    }
}

8

为什么要维护最小值,栈顶元素不就是最小值吗

3

请问单调栈思路是什么样的,我是菜鸟,请教一下大神。我思考了单增栈和单减栈,但是没分析明白,,,,

3

和接雨水一个思路

2

等价于581最短无序子数组,找到中间最短乱序之后,两侧的数就都符合比一侧全都大而比另一侧全都小的要求;只是边界条件有所不同,面试题要求的是严格递增序列

2

第二个例子???

2

分享一下自己写的采用单调栈的方法(只能测试一些简单样例,不保证完全正确)

public class Demo {
	public static void main(String[] args) {
		int[] nums = new int[] {9,10,8,7,3,5,4,2,1} ;
		Deque<Integer> stack = new LinkedList<>() ;
		int min = Integer.MAX_VALUE ;
		for(int i=0;i<nums.length;i++) {
			while(!stack.isEmpty()&&stack.peek()<=nums[i]){
				stack.pop() ;
			}
			if(i==0||nums[i]<min) {
				stack.push(nums[i]);
			}
			min = Math.min(min, nums[i]) ;
		}
		while(!stack.isEmpty()) {
			System.out.println(stack.pop());
		}
	}

}

其实楼主的这个方法,是不是可以预先把leftMin和rightMin求出来,之后再遍历一次数组,求出最后答案,这样时间复杂度也是0(N),空间复杂度也为O(N)

1
#include <iostream>
#include <vector>
#include <stack>
#include <iterator>

using namespace std;

class Solution{
public:

    vector<int> solve(vector<int>& nums){
        vector<int> ret;
        stack<int> decreaseSt;
        stack<int> increaseSt;
        int len = nums.size();
        bool *greaterThanRight = new bool[len];
        bool *smallerThanLeft = new bool[len];

        //使用单调递减栈,从左边开始遍历,判断元素是否比右边元素大
        decreaseSt.push(0);
        for(int i=0; i<len&&(!decreaseSt.empty());i++){
            if(nums[i]<nums[decreaseSt.top()]){
                greaterThanRight[decreaseSt.top()] = true;
            }else{
                while ((!decreaseSt.empty()) && nums[i]>=nums[decreaseSt.top()]){
                    greaterThanRight[decreaseSt.top()] = false;
                    decreaseSt.pop();
                }
            }
            decreaseSt.push(i);
        }
        //使用单调递增栈,从右边开始遍历,判断元素是否比左边元素小
        increaseSt.push(len-1);
        for(int j=len-1; j>=0&&(!increaseSt.empty());j--){
            if(nums[j]>nums[increaseSt.top()]){
                smallerThanLeft[increaseSt.top()] = true;
            }else{
                while((!increaseSt.empty()) && nums[j]<=nums[increaseSt.top()]){
                    smallerThanLeft[increaseSt.top()] = false;
                    increaseSt.pop();
                }
            }
            increaseSt.push(j);
        }
        greaterThanRight[len-1] = true;
        smallerThanLeft[0] = true;
        for(int i=0; i<len; i++){
            if(greaterThanRight[i] && smallerThanLeft[i]){
                ret.push_back(nums[i]);
            }
        }
        return ret;
    }
};

int main() {
    Solution sol;
    int arr[] = {9,8,7,3,4,2,1};
    vector<int> nums(arr,arr+7);
    vector<int> ret = sol.solve(nums);
    copy(ret.begin(),ret.end(),ostream_iterator<int>(cout," "));
    return 0;
}

1

想清楚了,栈可能出现pop掉所有元素导致栈顶为空的情况

1