Show problems as
Classic problem #135HardArrayGreedy

Candy

Real-world version: Pipeline Patrol Walks
Tracked in this browser only
Read Candy on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A pipeline runs past n inspection posts laid out in a single line and numbered from left to right. risk[i] is the hazard score logged at post i.

A shift plan hands every post a whole number of walk-throughs. Such a plan is signed off only when both of these hold:

  • No post is skipped: each one receives at least one walk-through.
  • Wherever a post's hazard score beats the score of a post standing immediately beside it, the plan hands that post strictly more walk-throughs than it hands the lower-scoring neighbour.

Two posts side by side on the same score place no requirement on each other.

Return the smallest total number of walk-throughs a signed-off plan can use.

Examples

Example 1

Input
risk = [3, 5, 5, 2]
Output
6

The plan 1, 2, 2, 1 is signed off: post 1 beats post 0 and walks more than it, post 2 beats post 3 and walks more than it, and posts 1 and 2 share a score so neither owes the other anything. The walk-throughs add up to 6.

Example 2

Input
risk = [8, 6, 4]
Output
6

Under the plan 3, 2, 1 post 0 walks more often than post 1 and post 1 walks more often than post 2, each of which it outscores, and no post drops below one walk-through. The total is 6.

Example 3

Input
risk = [2, 7, 9, 4]
Output
7

Take the plan 1, 2, 3, 1. Posts 1 and 2 each beat the post on their left and walk once more than it, while post 3 sits below post 2 in score and takes a single walk-through. Total 7.

Example 4

Input
risk = [0, 0, 0]
Output
3

All three scores match, so no post owes another extra walk-throughs, and the plan 1, 1, 1 clears both rules with a total of 3.

Constraints

  • n == risk.length
  • 1 <= n <= 5 * 10^4
  • 0 <= risk[i] <= 5 * 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_patrol_walks(risk: list[int]) -> int:
Java
public int minPatrolWalks(int[] risk)

More on the same topics