From January 2015, she started to practice leetcode questions; she trains herself to stay focus, develops "muscle" memory when she practices those questions one by one.
2015年初, Julia开始参与做Leetcode, 开通自己第一个博客. 刷Leet code的题目, 她看了很多的代码, 每个人那学一点, 也开通Github, 发表自己的代码, 尝试写自己的一些体会.
She learns from her favorite sports – tennis, 10,000 serves practice builds up good memory for a great serve. Just keep going.
Hard work beats talent when talent fails to work hard.
Saturday, October 3, 2020
Hard level: 862. Shortest Subarray with Sum at Least K
We can rephrase this as a problem about the prefix sums of A. Let P[i] = A + A + ... + A[i-1]. We want the smallest y-x such that y > x and P[y] - P[x] >= K.
Motivated by that equation, let opt(y) be the largest x such that P[x] <= P[y] - K. We need two key observations:
If x1 < x2 and P[x2] <= P[x1], then opt(y) can never be x1, as if P[x1] <= P[y] - K, then P[x2] <= P[x1] <= P[y] - K but y - x2 is smaller. This implies that our candidates x for opt(y) will have increasing values of P[x].
If opt(y1) = x, then we do not need to consider this x again. For if we find some y2 > y1 with opt(y2) = x, then it represents an answer of y2 - x which is worse (larger) than y1 - x.
Maintain a "monoqueue" of indices of P: a deque of indices x_0, x_1, ... such that P[x_0], P[x_1], ... is increasing.
When adding a new index y, we'll pop x_i from the end of the deque so that P[x_0], P[x_1], ..., P[y] will be increasing.
If P[y] >= P[x_0] + K, then (as previously described), we don't need to consider this x_0 again, and we can pop it from the front of the deque.