3113. Find the Number of Subarrays Where Boundary Elements Are Maximum

#php #leetcode #algorithms #programming

Hard

You are given an array of positive integers nums.

Return the number of subarrays¹ of nums, where the first and the last elements of the subarray are equal to the largest element in the subarray.

Example 1:

Input: nums = [1,4,3,3,2]
Output: 6
Explanation: There are 6 subarrays which have the first and the last elements equal to the largest element of the subarray: subarray [1,4,3,3,2], with its largest element 1. The first element is 1 and the last element is also 1. subarray [1,4,3,3,2], with its largest element 4. The first element is 4 and the last element is also 4. subarray [1,4,3,3,2], with its largest element 3. The first element is 3 and the last element is also 3. subarray [1,4,3,3,2], with its largest element 3. The first element is 3 and the last element is also 3. subarray [1,4,3,3,2], with its largest element 2. The first element is 2 and the last element is also 2. subarray [1,4,3,3,2], with its largest element 3. The first element is 3 and the last element is also 3.

Hence, we return 6.

Example 2:

Input: [3,3,3]
Output: 6
Explanation:
There are 6 subarrays which have the first and the last elements equal to the largest element of the subarray:
- subarray [3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.
- subarray [3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.
- subarray [3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.
- subarray [3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.
- subarray [3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.
- subarray [3,3,3], with its largest element 3. The first element is 3 and the last element is also 3.

Hence, we return 6.

Example 3:

Input: nums = [1]
Output: 1
Explanation: There is a single subarray of nums which is [1], with its largest element 1. The first element is 1 and the last element is also 1.

Hence, we return 1.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

Constraints:

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function numberOfSubarrays($nums) {
        $stack = [];
        $res = 0;

        for ($r = 0; $r < count($nums); $r++) {
            while ($stack && $stack[count($stack) - 1][0] < $nums[$r]) {
                array_pop($stack);
            }

            if ($stack && $stack[count($stack) - 1][0] == $nums[$r]) {
                $stack[count($stack) - 1][1]++;
            } else {
                array_push($stack, [$nums[$r], 1]);
            }

            $res += $stack[count($stack) - 1][1];
        }

        return $res;
    }
}

Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!