题意

在一条数轴上，有n个城市，编号从0 ~ n – 1 , 约翰打算在这n个城市做点生意，他对Armani的一批货物感兴
趣，每个城市对于这批货物都有一个价格prices[i]。对于城市x,约翰可从城市编号为[x - k, x + k]购买货物，然后
卖到城市x,问约翰在每个城市最多能赚到多少钱？

样例

给出 prices = [1, 3, 2, 1, 5], k = 2,返回 [0, 2, 1, 0, 4]。
解释：
i = 0，约翰可去的城市有0~2因为1、2号城市的价格比0号城市的价格高，所以赚不了钱，即 ans[0] = 0。
i = 1，可去的城市有0~3，可以从0号或者3号城市购买货物赚取的差价最大，即ans[1] = 2。
i = 2，可去的城市有0~4，显然从3号城市购买货物赚取的差价最大，即ans[2] = 1。
i = 3，可去的城市有1~4，没有其他城市的价格比3号城市价格低，所以赚不了钱，ans[3] = 0。
i = 4，可去的城市有2~4，从3号城市购买货物赚取的差价最大，即ans[4] = 4。

给出 prices = [1, 1, 1, 1, 1], k = 1, 返回 [0, 0, 0, 0, 0]。
解释：
所有城市价格都一样，所以不能赚到钱，即所有的ans都为0。

1.解题思路

  这是一道非常典型的线段树题。之前我也做过类似的题，Java 算法-区间求和I(线段树),其实原理都是差不多的。重点在于构建线段树，这里构造的线段树，用来记录每个区域的最小值。在最大的差价是，我只要在这个范围找到最小值，然后求最小值就行了。

2.代码

 public int[] business(int[] A, int k) {
        SegmentTreeNode node = build(A, 0, A.length - 1);

        int a[] =  new int[A.length];
        for(int i = 0; i < a.length; i++){
            SegmentTreeNode n = node;
            int min = Math.max( i -k, 0);
            int max = Math.min(i + k, A.length - 1);
            a[i] = Math.max( A[i]  - query(node, min, max), 0);
        }
        return a;
    }


    class SegmentTreeNode {
        public int start = 0;
        public int end = 0;
        public int min = 0;
        public SegmentTreeNode left = null;
        public SegmentTreeNode right = null;

        public SegmentTreeNode(int start, int end, int min) {
            this.start = start;
            this.end = end;
            this.min = min;
        }

    }
    //构建线段树
    private SegmentTreeNode build(int A[], int start, int end) {
        SegmentTreeNode node = new SegmentTreeNode(start, end, A[0]);
        if (node.start == node.end) {
            node.min = A[start];
            return node;
        }
        int mid = (node.start + node.end) / 2;
        node.left = build(A, start, mid);
        node.right = build(A, mid + 1, end);
        node.min = Math.min(node.left.min, node.right.min);
        return node;
    }
    //查询线段树
    private int query(SegmentTreeNode node, int start , int end) {
        if(start > end) {
            return 0;
        }
        if(node.start == start && node.end == end) {
            return node.min;
        }
        int mid = (node.start + node.end) / 2;
        if(end <= mid) {
            return query(node.left, start, end);
        }
        else if(start > mid) {
            return query(node.right, start, end);
        }else {
            //求最小值
            return Math.min(query(node.left, start, mid), query(node.right, mid + 1, end));
        }
    }