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


പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ അമേരിക്കൻ എക്സ്പ്രസ് ആപ്പിൾ ബൈറ്റ്ഡാൻസ് കോട്ട ഗൂഗിൾ ഇന്റൽ ലിങ്ക്ഡ് മാത്ത് വർക്ക്സ് മൈക്രോസോഫ്റ്റ് ഒറാക്കിൾ പേപാൽ Quora Salesforce സ്പ്ലങ്ക് ടെസ്ല ട്വിలియో ട്വിറ്റർ രണ്ട് സിഗ്മ യൂബർ വിഎംവെയർ Yelp
Bookin.com വിഭാഗങ്ങൾ - ഹാർഡ് ക്രൂയിസ് ഓട്ടോമാറ്റിൻ instacart tiktokകാഴ്ചകൾ 6

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

സ്ലൈഡിംഗ് വിൻഡോ മാക്സിമം ലീറ്റ്കോഡ് സൊല്യൂഷൻ പറയുന്നു - നിങ്ങൾക്ക് പൂർണ്ണസംഖ്യകളുടെ ഒരു നിര നൽകിയിരിക്കുന്നു 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 <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

അൽഗോരിതം -

ഐഡിയ -

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

സമീപനം -

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

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

സ്ലൈഡിംഗ് വിൻഡോ പരമാവധി LeetCode പരിഹാരംമൊട്ടുസൂചി സ്ലൈഡിംഗ് വിൻഡോ പരമാവധി LeetCode പരിഹാരംമൊട്ടുസൂചി സ്ലൈഡിംഗ് വിൻഡോ പരമാവധി LeetCode പരിഹാരംമൊട്ടുസൂചി സ്ലൈഡിംഗ് വിൻഡോ പരമാവധി LeetCode പരിഹാരംമൊട്ടുസൂചി

 

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

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

Translate »