库存跨度问题

Question

股票跨度问题是一个金融问题，在这个问题中，我们有一系列的n个股票的每日报价，我们需要计算所有n天的股票价格跨度。在给定的一天，股票价格的跨度i被定义为在给定的一天之前的连续的最大天数，对于这一天，股票的价格低于或等于它在给定的一天的价格。例如，如果7天价格的数组为{100、80、60、70、60、75、85}，则相应7天的跨度值为{1、1、1、2、1、4、6}。

寻找代码评审、优化和最佳实践。

public final class StockSpan {

    private StockSpan() {}

    public static int[] stockSpan(int[] stock) {
        // we will use stack for indexes and not for "stock values"
        final Stack<Integer> stack = new Stack<Integer>();
        int[] span = new int[stock.length];

        for (int i = 0; i < stock.length; i++) {
            int index = 0;
            span[i] = 1;
            while (!stack.isEmpty() && stock[stack.peek()] <= stock[i]) {
                index = stack.pop();
                span[i] = i - index + span[index];
            }
            stack.push(i);
        }

        return span;
    }
}

public class StockSpanTest {

    @Test
    public void test1() {
        int price1[] = {100, 80, 60, 70, 60, 75, 85};
        int expected1[] = {1, 1, 1, 2, 1, 4, 6};
        assertTrue(Arrays.equals(expected1, StockSpan.stockSpan(price1)));  
    }


    @Test
    public void test2() {
        int price2[] = {10, 4, 5, 90, 120, 80};
        int expected2[] = {1, 1, 2, 4, 5, 1};
        assertTrue(Arrays.equals(expected2, StockSpan.stockSpan(price2)));
    }
}

Answer 1

这里的基本算法看起来不错..。虽然堆栈的使用过度了。没有必要保留以前的成员。实际上，使用您在前面的循环中学到的，使用一个简单的while循环就可以了。

考虑到这一点：

public static int[] stockSpan(int[] stock) {
    // we will use stack for indexes and not for "stock values"
    int[] span = new int[stock.length];

    for (int i = 0; i < stock.length; i++) {
        int index = i - 1;
        span[i] = 1;
        while (index >= 0 && stock[index] <= stock[i]) {
            // previous member is the same or smaller price.
            // that member, plus all of its span, are also smaller.
            span[i] += span[index];
            // we can skip the span and check if the next span is smaller too.
            index -= span[index];
        }
    }

    // System.out.printf("Input %s -> SPans %s%n",
    //        Arrays.toString(stock), Arrays.toString(span));
    return span;
}

Answer 2

• 股票价格应该是双倍，而不是整数。
• 使用List，而不是数组。使用数组是非常古老的做法。编辑哎呀。见评论。
• 不需要堆栈：

public static List<Integer> findSpans(List<Double> stocks) {
    if (stocks.isEmpty())
        throw new IllegalArgumentException();
    List<Integer> spans = new ArrayList<>(stocks.size());
    for (int i = 0; i < stocks.size(); i++) {
        int span = 1;
        {
            int previousSpanIndex = i - 1;
            while (previousSpanIndex >= 0 && (stocks.get(i) >= stocks.get(previousSpanIndex))) {
                span += spans.get(previousSpanIndex);
                previousSpanIndex -= spans.get(previousSpanIndex);
            }
        }
        spans.add(span);
    }
    return spans;
}