題目描述

小Q在周末的時候和他的小伙伴來到大城市逛街吊圾，一條步行街上有很多高樓褒繁，共有n座高樓排成一行月劈。
小Q從第一棟一直走到了最后一棟喳篇，小Q從來都沒有見到這么多的樓越除，所以他想知道他在每棟樓的位置處能看到多少棟樓呢节腐？（當(dāng)前面的樓的高度大于等于后面的樓時，后面的樓將被擋渍琛）

輸入描述:

輸入第一行將包含一個數(shù)字n翼雀，代表樓的棟數(shù)，接下來的一行將包含n個數(shù)字wi(1<=i<=n)孩擂，代表每一棟樓的高度狼渊。
1<=n<=100000;
1<=wi<=100000;

輸出描述:

輸出一行，包含空格分割的n個數(shù)字vi类垦，分別代表小Q在第i棟樓時能看到的樓的數(shù)量狈邑。

輸入例子1:

6
5 3 8 3 2 5

輸出例子1:

3 3 5 4 4 4

例子說明1:

當(dāng)小Q處于位置3時，他可以向前看到位置2,1處的樓蚤认，向后看到位置4,6處的樓米苹，加上第3棟樓，共可看到5棟樓砰琢。當(dāng)小Q處于位置4時蘸嘶，他可以向前看到位置3處的樓，向后看到位置5,6處的樓氯析，加上第4棟樓亏较，共可看到4棟樓。

解題思路1-暴力法

一開始用到的方法是簡單粗暴的暴力法掩缓，結(jié)果只有60%的測試用例通過雪情，時間復(fù)雜度是 $O(n^2)$ ，明顯不符合題意你辣。

代碼

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        int nums[] = new int[count];
        int res[] = new int[count];

        int index = 0;
//        輸入數(shù)據(jù)
        while(count-->0){
            nums[index++] = scanner.nextInt();
        }
        int start, end;
        for(int i=0;i<index;i++){
            int result = 0;
            int low = 0,up=0;
            start = i-1;
            end = i+1;
            if(start>=0){
                low = nums[start];
                result++;
            }
            start--;
            while(start>=0){
                if(nums[start]>low){
                    result++;
                    low = nums[start];

                }
                start--;
            }
            if(end<index){
                up = nums[end];
                result++;
            }
            end++;
            while(end<index){
                if(nums[end]>up){
                    result++;
                    up = nums[end];

                }
                end++;
            }
            res[i] = result+1;

        }
        for(int i=0;i<index;i++)
            System.out.print(res[i] + " ");
        System.out.println();
    }

思路分析:

可以用到單調(diào)棧巡通，顧名思義就是棧里面的元素是單調(diào)遞增的，這樣的話只要判斷元素是否大于棧里面的元素就可以進(jìn)行判斷有多少棟樓比當(dāng)前的樓高舍哄。
例如：
5 3 8 3 2 5
我們用一個向前看的棧Stack進(jìn)行說明宴凉，他是個單調(diào)棧，里面所有的元素都是遞增的表悬，用數(shù)組left表示向前看有多少樓可以看到弥锄，例如left[1]=1表示在位置1向左邊看可以看到1棟樓。
遍歷數(shù)組：
i=0: left[0] = 0 stack = [5]
i=1: left[1] = 1 stack = [5,3]
i=2: left[2] = 2 stack = 8
i=3: left[3] =1 stack = [8,3]
i=4: left[4] =2 stack = [8,3,2]
i=5:left[5] = 3 stack = [8,5]（5的右邊還是可以看到8）

單調(diào)棧代碼

    public static void main(String[] args) {
    // write your code here
//        用戶輸入數(shù)據(jù)
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int []arr = new int[n];
//        賦值
        for(int i=0;i<n;i++)
            arr[i] = scanner.nextInt();
//        給定2個堆棧：分別向左邊右邊看齊
        Stack<Integer> left_stack = new Stack<>();
        Stack<Integer> right_stack = new Stack<>();

//        向左看和向右看的樓的數(shù)量
        int []left_count = new int[n],right_count = new int[n];
        int j=0;
        for(int i=0;i<n;i++){
//            從右邊到左邊看
            j = n-i-1;
            left_count[i] = left_stack.size();
            right_count[j] = right_stack.size();
//            如果當(dāng)前的數(shù)字比棧頂?shù)臄?shù)字還要大的話，就出棧籽暇，因為已經(jīng)被擋住了
            while(!left_stack.isEmpty() && left_stack.peek() <= arr[i])
                left_stack.pop();
            while(!right_stack.isEmpty() && right_stack.peek() <= arr[j])
                right_stack.pop();
            left_stack.push(arr[i]);
            right_stack.push(arr[j]);
        }
        for(int i=0;i<n;i++)
            System.out.print(left_count[i]+right_count[i]+1 + " ");
        System.out.println();
}

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者