1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

leetcode medium

#array#csharp#hash-table#heap#leetcode#math#medium#sliding-window#sort#string#two-pointers

Task

Дан массив целых чисел nums и целое число limit. Вернуть размер самой длинной непустой подстроки, такая что абсолютная разница между любыми двумя элементами этой подстроки меньше или равна limit.

Пример:

Input: nums = [8,2,4,7], limit = 4

Output: 2

Explanation: All subarrays are:

[8] with maximum absolute diff |8-8| = 0 <= 4.

[8,2] with maximum absolute diff |8-2| = 6 > 4.

[8,2,4] with maximum absolute diff |8-2| = 6 > 4.

[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.

[2] with maximum absolute diff |2-2| = 0 <= 4.

[2,4] with maximum absolute diff |2-4| = 2 <= 4.

[2,4,7] with maximum absolute diff |2-7| = 5 > 4.

[4] with maximum absolute diff |4-4| = 0 <= 4.

[4,7] with maximum absolute diff |4-7| = 3 <= 4.

[7] with maximum absolute diff |7-7| = 0 <= 4.

Therefore, the size of the longest subarray is 2.

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int LongestSubarray(int[] nums, int limit) {
        var maxHeap = new SortedSet<(int Value, int Index)>(Comparer<(int, int)>.Create((a, b) => a.Value == b.Value ? a.Index.CompareTo(b.Index) : b.Value.CompareTo(a.Value)));
        var minHeap = new SortedSet<(int Value, int Index)>(Comparer<(int, int)>.Create((a, b) => a.Value == b.Value ? a.Index.CompareTo(b.Index) : a.Value.CompareTo(b.Value)));
        int left = 0, maxLength = 0;
        for (int right = 0; right < nums.Length; ++right) {
            maxHeap.Add((nums[right], right));
            minHeap.Add((nums[right], right));
            while (maxHeap.Min.Value - minHeap.Max.Value > limit) {
                left = Math.Min(maxHeap.Min.Index, minHeap.Max.Index) + 1;
                while (maxHeap.Min.Index < left) {
                    maxHeap.Remove(maxHeap.Min);
                }
                while (minHeap.Max.Index < left) {
                    minHeap.Remove(minHeap.Max);
                }
            }
            maxLength = Math.Max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int LongestSubarray(vector<int>& nums, int limit) {
        var maxHeap = new SortedSet<(int Value, int Index)>(Comparer<(int, int)>.Create((a, b) => a.Value == b.Value ? a.Index.CompareTo(b.Index) : b.Value.CompareTo(a.Value)));
        var minHeap = new SortedSet<(int Value, int Index)>(Comparer<(int, int)>.Create((a, b) => a.Value == b.Value ? a.Index.CompareTo(b.Index) : a.Value.CompareTo(b.Value)));
        int left = 0, maxLength = 0;
        for (int right = 0; right < nums.size(); ++right) {
            maxHeap.push_back((nums[right], right));
            minHeap.push_back((nums[right], right));
            while (maxHeap.Min.Value - minHeap.Max.Value > limit) {
                left = min(maxHeap.Min.Index, minHeap.Max.Index) + 1;
                while (maxHeap.Min.Index < left) {
                    maxHeap.Remove(maxHeap.Min);
                }
                while (minHeap.Max.Index < left) {
                    minHeap.Remove(minHeap.Max);
                }
            }
            maxLength = max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}

Java solution

matched/original

import java.util.Comparator;
import java.util.PriorityQueue;

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>(
            (a, b) -> b[0] - a[0]
        );
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            Comparator.comparingInt(a -> a[0])
        );

        int left = 0, maxLength = 0;

        for (int right = 0; right < nums.length; ++right) {
            maxHeap.offer(new int[] { nums[right], right });
            minHeap.offer(new int[] { nums[right], right });

            while (maxHeap.peek()[0] - minHeap.peek()[0] > limit) {
                left = Math.min(maxHeap.peek()[1], minHeap.peek()[1]) + 1;
                while (maxHeap.peek()[1] < left) {
                    maxHeap.poll();
                }
                while (minHeap.peek()[1] < left) {
                    minHeap.poll();
                }
            }

            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

Go solution

matched/original

package main

import (
    "container/heap"
)

type IntHeap []int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool  { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{}   { old := *h; n := len(old); x := old[n-1]; *h = old[0 : n-1]; return x }

type MaxHeap struct{ IntHeap }
func (h MaxHeap) Less(i, j int) bool { return h.IntHeap[i] > h.IntHeap[j] }

func longestSubarray(nums []int, limit int) int {
    maxHeap := &MaxHeap{}
    minHeap := &IntHeap{}
    heap.Init(maxHeap)
    heap.Init(minHeap)

    left, maxLength := 0, 0

    for right, num := range nums {
        heap.Push(maxHeap, num)
        heap.Push(minHeap, num)

        for (*maxHeap)[0]-(*minHeap)[0] > limit {
            if (*maxHeap)[0] == nums[left] {
                heap.Pop(maxHeap)
            }
            if (*minHeap)[0] == nums[left] {
                heap.Pop(minHeap)
            }
            left++
        }

        if maxLength < right-left+1 {
            maxLength = right-left+1
        }
    }

    return maxLength
}

Explanation

Algorithm

1⃣Инициализировать два дека (minDeque и maxDeque) для хранения минимальных и максимальных значений в текущем окне и переменную left для начала окна.

2⃣Итеративно добавлять элементы в дек, поддерживая условие абсолютной разницы между максимальным и минимальным элементом в окне, чтобы она была не больше limit, при необходимости сдвигая left.

3⃣Обновлять maxLength, проверяя максимальную длину текущего окна, и возвращать maxLength как результат.

😎