这题和497类似，就是497的子集吧。
先取prefixSum, 然后random产生一个数，再做binarySearch
我们产生了随机数之后，要找一个能够cover这个数的矩形。就是矩形的prefixSum一定要比它大。
比如随机数 3，我们一定要找在prefixSum数组里找一个比它大的能盖住它的。
class Solution {
int[] prefixSum;
Random random;
public Solution(int[] w) {
prefixSum = new int[w.length];
for (int i = 0; i < w.length; i++) {
prefixSum[i] = w[i] + (i > 0 ? prefixSum[i - 1] : 0);
}
random = new Random();
}
public int pickIndex() {
int num = random.nextInt(prefixSum[prefixSum.length - 1]);
// find the smallest larger;
int l = 0, r = prefixSum.length - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (prefixSum[mid] <= num ) {
l = mid + 1;
} else {
r = mid;
}
}
return l;
}
}
