Jim和摩天大楼数据结构使用堆栈解决，但效率不高。

Question

问题链接:https://www.hackerrank.com/challenges/jim-and-the-skyscrapers

问题陈述让我们在一维空间中描述这个问题。我们总共有N座摩天大楼从左向右排列。这座摩天大楼的高度很高。一条飞行路线可以被描述为(i，j)和I HZ42 j，这意味着吉姆开始他的HZ42在摩天大楼I的顶部和降落在摩天大楼j。因为HZ42只能水平飞行，吉姆将只停留在高度hi。因此，路径(i，j)是有效的，只有当每一座摩天大楼i，i+1，.，j−1，j不是严格大于hi，并且他从摩天大楼出发和到达的摩天大楼的高度相同的情况下。形式上，(i，j)是当且仅当j:hk>hi，hi=hj，∄k∈i的当且仅当。

我的方法:

我用过堆栈。如果下一个整数小于堆栈顶部，则将其推入堆栈。如果它更大，则会弹出堆栈的顶部(第一个顶部)，并与堆栈顶部进行比较。如果它们相等，则增加计数器，再次弹出顶部，并将新的顶部与以前的堆栈(第一个顶部)顶部进行比较。过程被重复，直到堆栈的顶部(第一个顶部)不等于堆栈的顶部。

最后，如果堆栈不是空的，我将再次计算重复元素。特定元素的计数器动态存储在数组列表中。

，这是一个很好的方法吗？堆栈是正确的选择吗？我的代码可以临时编写来加速吗？

我的代码是正确的，但由于超时，很少有测试用例被终止。

输入格式

第一行包含N，摩天大楼的数量。下一行包含N个分隔整数，表示摩天大楼的高度。

输出格式

打印一个整数，表示有效路由的数目。

我的代码：

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    // method to calculate nCr
    public static long choose(long total, long choose){ 
        if(total < choose)
            return 0;
        if(choose == 0 || choose == total)
            return 1;
        return choose(total-1,choose-1)+choose(total-1,choose);
    }

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int count = 1;
        long x = 0;
        Stack s = new Stack();
        ArrayList<Integer> alist = new ArrayList<Integer>();

        for(int i=0 ; i<t ; i++){
            int a = sc.nextInt();
            if(s.isEmpty() || ((int)s.peek()>= a) ){
                s.push(a);
            } else {
                    while(!(s.isEmpty()) && a > (int)s.peek() ){
                    int top = (int)s.pop();
                        while(!(s.isEmpty()) && top == (int)s.peek()){
                        count++;
                        s.pop();
                    }
                    if(count>1){
                        alist.add(count);
                        count=1;
                    }
             }
                s.push(a);
             }
        }

         while(!(s.isEmpty()) ){
                 int tp = (int)s.pop();
                    while(!(s.isEmpty()) && tp == (int)s.peek()){
                        count++;
                        s.pop();
                    }
                    if(count>1){
                          alist.add(count);
                          count=1;
                    }
               }

       for(Integer n : alist){
           x += choose(n,2);
       }

       System.out.println(2*x);
    }
}

Answer 1

在我看来，你的方法有点复杂，而且(因此)费时。

这里有一个替代方案，我怀疑它是否会使用任何相关的时间-在VB中；我相信你可以用任何你喜欢的语言翻译它。我只介绍该方法的“心脏”(不处理输入和输出)。

Dim result As New SortedDictionary(Of Integer, List(Of Flight)) 'key: index of skyscraper where the flight starts.
Dim flightsWithSameStart As List(Of Flight) = Nothing 'placeholder
Dim hValue As Integer

Dim openFlights As New List(Of Flight)(hValues.Count) 'hValues is a list of (integer) skyscraper heights, provided by the user.

For indx As Integer = 0 To hValues.Count - 1

  hValue = hValues(indx)

  Dim n As Integer = openFlights.Count
  For k As Integer = n - 1 To 0 Step -1

    Dim fl As Flight = openFlights(k)

    If hValue > fl.height Then

      ' Remove the Flight: it cannot continue and (apparently) it hasn't landed.
      openFlights.RemoveAt(k)

    ElseIf hValue = fl.height Then
      ' This flight will branch:
      ' a) it can stop here, landing at this height.
      ' b) it can also continue.
      ' We achieve this by storing a CLONE of the current flight and NOT removing this current flight from the open flights.

      Dim flCopy As Flight = fl.Clone
      flCopy.last = indx
      If Not result.TryGetValue(flCopy.first, flightsWithSameStart) Then
        flightsWithSameStart = New List(Of Flight)
        result.Add(flCopy.first, flightsWithSameStart)
      End If
      flightsWithSameStart.Add(flCopy)

    Else
      Exit For
    End If

  Next

  ' At each skyscraper we hopefully launch another flight.
  Dim flNew As New Flight
  flNew.first = indx
  flNew.height = hValue
  openFlights.Add(flNew)

Next

' Discard any remaining open flights: they cannot land.
' (just ignore whatever is left in 'openFlights')

使用了一个简单的助手类class：

私舱飞行

Public first As Integer
Public last As Integer
Public height As Integer

Public Function Clone() As Flight
  Dim copy As Flight = CType(Me.MemberwiseClone, Flight)
  Return copy
End Function

端级

如果我犯了错误(或者可能误解了问题)，请道歉--只是运行几个测试案例，在我看来它们似乎还可以。

问候

(忘了提到，每当i=>j是有效的路径/飞行时，j=>i也是如此，就像我的代码中那样，用j>i计算这些情况就足够了(如果您愿意的话，也可以倒转它们以添加镜像)。