Golang solution using slice as deque


  • 0

    I assume using slice can produce the same result without using /container/list, please correct me if I'm wrong.
    deque is a slice but emulates deque. We maintain the array while iterating nums so that

    1. Always deque[0] is the index of the largest value so far, 
       and indexes of other "promising" values follow in descending order of their values.
    2. Discard deque[0] if nums[deque[0]] is out of window range
    3. Compare nums[i] and nums[deque[0]], and
       (case A) if nums[i] >= nums[deque[0]]: 
         nums[i] is the largest and since i is the rightmost index so far,
         no other values in deque have chance to be largest.
         Thus we can discard all deque content and can have []int{i} as a new deque
       (case B) else if nums[i] < nums[deque[end]]: 
         nums[i] is the smallest value so far, but it still could be the maximum value in future,
         so append it to the right side of deque.
       (case C) else if nums[i] > nums[deque[end]]:
         nums[i] is not the largest but it may be the maximum value in future (promising than the case above😀).
         Values whose index is in deque and smaller than nums[i] has no chance to be the maximum value,
         so discard them all from left of deque and add nums[i] at the last of deque.
         insert func does the job.
    
    func maxSlidingWindow(nums []int, k int) []int {
    	nlen := len(nums)
    	if nlen == 0 {
    		return []int{}
    	}
    
    	// get initial deque from nums[0:k-1]
    	deque := []int{0}
    	for i := 1; i < k; i++ {
    		if len(deque) == 0 || nums[i] >= nums[deque[0]] { // case A
    			deque = []int{i}
    		} else if nums[i] < nums[deque[len(deque)-1]] { // case B
    			deque = append(deque, i)
    		} else {
    			insert(&deque, nums, i) // case C
    		}
    	}
    
    	// proceed and update deque
    	res := make([]int, nlen-k+1)
    	res[0] = nums[deque[0]]
    	for i := 1; i < nlen-k+1; i++ {
    		idx := i + k - 1
    
    		if deque[0] < i { // discard if out of window range
    			deque = deque[1:]
    		}
    
    		if len(deque) == 0 || nums[idx] >= nums[deque[0]] { // case A
    			deque = []int{idx}
    			res[i] = nums[idx]
    		} else if nums[idx] < nums[deque[len(deque)-1]] { // case B
    			res[i] = nums[deque[0]]
    			deque = append(deque, idx)
    		} else {
    			res[i] = nums[deque[0]]
    			insert(&deque, nums, idx) // case C
    		}
    	}
    	return res
    }
    
    // insert inserts nums[index] to deque while searching a place to insert 
    // and discard all smaller values. Looks little messy but we update length of slice, so need to use a pointer.
    func insert(pdeque *[]int, nums []int, index int) {
    	deque := *pdeque
    	j := len(deque) - 1
    	for nums[index] >= nums[deque[j]] {
    		j--
    	}
    	deque[j+1] = index
    	deque = deque[:j+2]
    	*pdeque = deque
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.