Hackerearth感觉更高

Question

链接到问题-> https://www.hackerearth.com/practice/data-structures/stacks/basics-of-stacks/practice-problems/algorithm/feel-taller/

我的代码或逻辑有什么问题？

我使用堆栈跟踪比当前建筑高的建筑数量，从上一栋楼开始。我通过跟踪堆栈中的元素数(比当前元素更高的元素)来做到这一点。

在查询中，我从右边减去左边，然后添加1.左->数，从左到右可以看到的->数，从右边可以看到的建筑数，如果减去两者，我们得到的建筑数比在范围内看到的要多。

举个例子:有7根柱子(k)，每根柱子的高度是5，2，3，7，9，8，11。使用堆栈，我跟踪的柱子数量大于当前的支柱(在其上方可见)，并将其存储在数组p中。其值为(当前柱高)->(柱数大于此柱) 5->3 ->4 3->3 7->2 9->1 8->1 11->0。在查询中，我从左减去右，因为左的柱状数大于当前的柱状数，如果右方减去，就得到了范围内的支柱。

我想知道这个逻辑有什么问题.

对这一问题有不同的解决办法，我知道这一点。请告诉我这个密码有什么问题。

链接到我的代码 -> https://www.hackerearth.com/submission/42773897/

//https://www.hackerearth.com/practice/data-structures/stacks/basics-of-stacks/practice-problems/algorithm/feel-taller/
//Feel Taller
import java.util.*;
import java.io.*;
public class Feel_Taller{
    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int k = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());

        long a[] = new long[k];
        for(int i=0;i<k;i++)
            a[i] = Long.parseLong(st.nextToken());

        Stack<Integer> s = new Stack<Integer>();
        int n = 0;                              //Number of elements in the stack
        int p[] = new int[k];                   //Number of pillars greater than this pillar

        for(int i = k-1;i>=0;i--)
        {
            while(!s.empty() && a[s.peek()]<=a[i]){
                s.pop();
                n--;
            }
            p[i] = n;
            s.push(i);
            n++;
        }

        //Queries
        int q = Integer.parseInt(br.readLine().trim());
        while(q-->0){
            st = new StringTokenizer(br.readLine().trim());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            if(r>=k)
                r = k-1;
            sb.append(p[l]-p[r]+1).append("\n");
        }

        pw.print(sb);
        pw.flush();
        pw.close();
    }
}

或者请解释我们如何用我的方法来解决这个问题。谢谢。

Answer 1

如果没有研究过您的代码，这就是您的逻辑似乎出了问题的地方:您的减法并不总是会给出正确的结果。

考虑一下这一排建筑物或柱子：

7 3 5

现在我相信你的高柱数应该是7->0 ->1和5->0。

当我查询范围0，1，答案应该是1:只有7个高楼是可见的。减法p[l]-p[r]+1产生0-1+1= 0，所以一栋建筑太少了.一种说法是，你减去5幢高楼的1，因为它超出了被查询的范围，但那座建筑从一开始就看不见，所以不应该减去。