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

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

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;


    }
}

26
该内容已被删除

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

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());
        }
    }
}

7
展开全部 33 讨论