സ്ലൈഡിംഗ് വിൻഡോ പരമാവധി LeetCode പരിഹാരം

പ്രശ്നം പ്രസ്താവന

സ്ലൈഡിംഗ് വിൻഡോ മാക്സിമം ലീറ്റ്കോഡ് സൊല്യൂഷൻ പറയുന്നു - നിങ്ങൾക്ക് പൂർണ്ണസംഖ്യകളുടെ ഒരു നിര നൽകിയിരിക്കുന്നു nums, വലിപ്പമുള്ള ഒരു സ്ലൈഡിംഗ് വിൻഡോ ഉണ്ട് k അറേയുടെ ഇടതുവശത്ത് നിന്ന് വലതുവശത്തേക്ക് നീങ്ങുന്നത്. നിങ്ങൾക്ക് മാത്രമേ കാണാൻ കഴിയൂ k വിൻഡോയിലെ നമ്പറുകൾ. ഓരോ തവണയും സ്ലൈഡിംഗ് വിൻഡോ ഒരു സ്ഥാനത്തിലൂടെ വലത്തേക്ക് നീങ്ങുന്നു.

മടങ്ങുക പരമാവധി സ്ലൈഡിംഗ് വിൻഡോ.

ഉദാഹരണം 1:

ഇൻപുട്ട്:

 nums = [1,3,-1,-3,5,3,6,7], k = 3

ഔട്ട്പുട്ട്:

 [3,3,5,5,6,7]

വിശദീകരണം:

 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7

3

 1 [3  -1  -3] 5  3  6  7

3

 1  3 [-1  -3  5] 3  6  7

5

 1  3  -1 [-3  5  3] 6  7

5

 1  3  -1  -3 [5  3  6] 7

6

 1  3  -1  -3  5 [3  6  7]

7

ഉദാഹരണം 2:

ഇൻപുട്ട്:

 nums = [1], k = 1

ഔട്ട്പുട്ട്:

 [1]

നിയന്ത്രണങ്ങൾ:

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• 1 <= k <= nums.length

അൽഗോരിതം -

ഐഡിയ -

• • സ്ലൈഡിംഗ് വിൻഡോ പരമാവധി കണ്ടെത്തുന്നതിന്. ആദ്യം, ഞങ്ങൾ നൽകിയിരിക്കുന്ന ശ്രേണിയിൽ ശ്രദ്ധ കേന്ദ്രീകരിക്കും, അതായത് K, പരമാവധി ഘടകം ആ പരിധിക്കുള്ളിലാണ്. അടിസ്ഥാനപരമായി ഞങ്ങൾ ചെയ്യേണ്ടത് ഉത്തരം നൽകുന്ന ഒരു ഡിക്യൂ ആൻഡ് ആൻസർ ലിസ്റ്റ് ഉണ്ടാക്കുക എന്നതാണ്.
  • തുടർന്ന് അറേയിലൂടെ സഞ്ചരിക്കുകയും ഡിക്യൂവിന്റെ മുകൾഭാഗം നിലവിലെ മൂല്യത്തേക്കാൾ കുറവാണെങ്കിൽ അവസ്ഥ പരിശോധിക്കുകയും തുടർന്ന് ക്യൂവിൽ നിന്ന് എലമെന്റ് പോപ്പ് ഔട്ട് ചെയ്യുക അല്ലെങ്കിൽ എലമെന്റ് സൂചികയെ ഡിക്യൂവിലേക്ക് തള്ളുക.
  • പരമാവധി ഘടകം പരിധിക്കുള്ളിൽ കിടക്കുന്നില്ലെങ്കിൽ വീണ്ടും രണ്ട് വ്യവസ്ഥകൾ ഞങ്ങൾ പരിശോധിക്കും, അത് ഡീക്യൂവിൽ നിന്ന് പോപ്പ് ഔട്ട് ചെയ്യുക, ഒരു വ്യവസ്ഥ കൂടി നൽകുക, അതായത് സൂചിക K-1 നേക്കാൾ വലുതോ തുല്യമോ ആണെങ്കിൽ, ഞങ്ങൾ ചെയ്യും. ഞങ്ങളുടെ ഉത്തര ലിസ്റ്റ് പൂരിപ്പിക്കാൻ തുടങ്ങുക, അതിൽ ആദ്യത്തെ ഘടകത്തിന്റെ ഡീക്യൂ ചേർക്കുകയും അവസാനം ഉത്തരം നൽകുകയും ചെയ്യുക.

സമീപനം -

• ആദ്യം, ഞങ്ങൾ ഒരു ഡീക്കും ഒരു ഉത്തര ലിസ്റ്റും സൃഷ്ടിക്കും, അവസാനം ഞങ്ങൾ ഉത്തരം നൽകും.
• അതിനുശേഷം, ഞങ്ങൾ മുഴുവൻ അറേയിലൂടെയും സഞ്ചരിക്കും, ഒപ്പം while അവസ്ഥയുടെ സഹായത്തോടെ, q[-1] < നിലവിലെ val ഈ അവസ്ഥ തൃപ്തികരമാണെങ്കിൽ, q-ൽ നിന്ന് അവസാന ഘടകം പോപ്പ് ഔട്ട് ചെയ്യുമോ എന്ന് ഞങ്ങൾ പരിശോധിക്കും. അല്ലെങ്കിൽ മൂലക സൂചിക q ലേക്ക് തള്ളുക.
• തുടർന്ന് ഞങ്ങൾ സൂചിക - K == q[0] ഉപയോഗിച്ച് പരമാവധി ഘടകം പരിധിക്കുള്ളിലാണോ അല്ലയോ എന്ന് പരിശോധിക്കും. വ്യവസ്ഥ തൃപ്തികരമാണെങ്കിൽ, q.popleft() ഉപയോഗിച്ച് q-ൽ നിന്ന് മൂലകം പോപ്പ് ചെയ്യും.
• സൂചിക K-1 ന് തുല്യമാണോ അതോ K-1 നേക്കാൾ വലുതാണോ എന്ന് വീണ്ടും പരിശോധിക്കുക, തുടർന്ന് ഉത്തര പട്ടികയിൽ പരമാവധി ഘടകം ചേർത്ത് ഉത്തരം നൽകുക.
• അതിനാൽ നമ്മൾ സ്ലൈഡിംഗ് വിൻഡോ മാക്സിമം കണ്ടെത്തും.

പരിഹാരത്തിന്റെ ചിത്രം -

മൊട്ടുസൂചി മൊട്ടുസൂചി മൊട്ടുസൂചി മൊട്ടുസൂചി

 

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        q = deque()
        
        for i,v in enumerate(nums):
            
              while(q and nums[q[-1]] <= v):
                    q.pop()
              
              q.append(i)
                
              
              if q[0] == i-k:
                    q.popleft()
              
            
              if i >= k-1:
                    ans.append(nums[q[0]])
        return ans

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) {
            return nums;
        }
        int[] ans = new int[n - k + 1];
        LinkedList<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (!q.isEmpty() && q.peek() < i - k + 1) {
                q.poll();
            }
            while (!q.isEmpty() && nums[i] >= nums[q.peekLast()]) {
                q.pollLast();
            }
            q.offer(i);
            if (i - k + 1 >= 0) {
                ans[i - k + 1] = nums[q.peek()];
            }
        }
        return ans;
    }
}

സമയ സങ്കീർണ്ണത: O(N), ഞങ്ങൾ ഒരു പ്രാവശ്യം മാത്രമേ മുഴുവൻ അറേയും സഞ്ചരിച്ചിട്ടുള്ളൂ.

ബഹിരാകാശ സങ്കീർണ്ണത: O(N), ഞങ്ങൾ ഒരു Deque സൃഷ്ടിച്ചതുപോലെ.

സമാനമായ ചോദ്യങ്ങൾ - https://www.tutorialcup.com/interview/algorithm/sliding-window-technique.htm

മുൻനിര സ്ലൈഡിംഗ്-വിൻഡോ-മാക്സി അഭിമുഖ ചോദ്യങ്ങൾ