题意

在一条数轴上，有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));        }    }

原著是一个有趣的人,若有侵权,请通知删除