A Mountaineer 最详细的解题报告

题目来源：A Mountaineer （不知道该链接是否可以直接访问，所以将题目复制下来了）

题目如下：

D - A Mountaineer

---

Time limit : 2sec / Stack limit : 256MB / Memory limit : 256MB

Problem

Dave is a mountaineer. He is now climbing a range of mountains.

On this mountains, there are N huts located on a straight lining from east to west..

The huts are numbered sequentially from 1 to N. The west most hut is 1, the east most hut is N. The i-th hut is located at an elevation of hi meters.

Dave wants to know how many huts he can look down and see from each hut.

He can see the j-th hut from the i-th hut if all huts between the i-th hut and the j-th hut including the j-th one are located at equal or lower elevation than hi.

Note that the i-th hut itself is not included in the hut he can see from the i-th hut.

---

Input

The input will be given in the following format from the Standard Input.

N
h1
h2
:
hN

• On the first line, you will be given N(1≦N≦105), the number of huts.
• Then N lines follow, each of which contains hi(1≦hi≦105) the elevation of the i-th hut.

---

Achievements and Points

Your answer will be checked for two levels.

• When you pass every test case which satisfies 1≦N≦3,000, you will be awarded 30 points.
• In addition, if you pass all the rest test cases which satisfy 1≦N≦105, you will be awarded 70 more points, summed up to 100points.

---

Output

On the i-th line, output the number of huts Dave can see from the i-th hut. Make sure to insert a line break at the end of the output.

---

Input Example 1

3
1
2
3

Output Example 1

0
1
2

From each hut he can see every huts on the west.

---

Input Example 2

5
1
2
3
2
1

Output Example 2

0
1
4
1
0

From the 1st and 5th hut he can't see any other huts.

From the 2nd hut he can only see the 1st hut.

From the 4th hut he can only see the 5th hut.

From the 3rd hut he can see every other huts.

---

Input Example 3

5
3
2
1
2
3

Output Example 3

4
2
0
2
4

Note that he can see the huts on the equal elevation.

---

Input Example 4

8
4
3
2
3
4
3
2
1

Output Example 4

7
2
0
2
7
2
1
0

由于题目比较简单，所以就不翻译了。

算法一解题思路（时间复杂度O(n^2)）

假设输入序列为 a1,a2,...,ai-1,ai,ai+1,...,an，如果要求ai所能看见的huts个数，则需要依次统计ai左边和右边小于ai的个数和。

具体算法（java版，TLE）

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }
        for (int i = 0; i < n; i++) {
            int value = array[i];
            int count = 0;
            int j = i - 1;
            int k = i + 1;
            while (j >= 0 && array[j] <= value) {
                count++;
                j--;
            }
            while (k < n && array[k] <= value) {
                count++;
                k++;
            }
            System.out.println(count);
        }
    }
}

算法二解题思路（时间复杂度O(n)）

分析一下算法一为什么会比较慢，其主要原因是会有大量重复的计算。假设我们已经知道ai-1左边小于ai-1的huts个数m了，如果ai大于ai-1，则ai左边huts的个数一定大于等于m+1，我们不妨将下标从ai-1向左移动m位，然后再比较ai与n=ai-m-1所对应的值，如果ai对应的值大于等于n对应的值，依次计算。然后用同样的方法计算右边的值，最后将左边和右边的值相加就可以得到正确结果。

具体算法（java版，直接AC）

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = scanner.nextInt();
        }
        int[] ansLeft = new int[n];
        int[] ansRight = new int[n];
        for (int i = 0; i < n; i++) {
            int value = array[i];
            if (i > 0) {
                int k = i - 1;
                if (value < array[k]) {
                    ansLeft[i] = 0;
                } else {
                    while (k >= 0 && array[k] <= value) {
                        ansLeft[i] += ansLeft[k] + 1;
                        k = k - ansLeft[k] - 1;
                    }
                }
            }
        }
        for (int i = n - 1; i >= 0; i--) {
            int value = array[i];
            if (i < n - 1) {
                int k = i + 1;
                if (value < array[k]) {
                    ansRight[i] = 0;
                } else {
                    while (k < n && array[k] <= value) {
                        ansRight[i] += ansRight[k] + 1;
                        k = k + ansRight[k] + 1;
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            System.out.println(ansLeft[i] + ansRight[i]);
        }
    }
}