查找“X”形图案的总数

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

void performDFS(vector<vector<char>> &matrix, int p, int q) {
    if (p < 0 || q < 0 || p >= matrix.size() || matrix[p].size() <= q) {
        return;
    }
    if (matrix[p][q] == 'X') {
        // Update element with 'O'
        matrix[p][q] = 'O';
        // Recursively call DFS in all 4 directions
        performDFS(matrix, p + 1, q);
        performDFS(matrix, p, q + 1);
        performDFS(matrix, p - 1, q);
        performDFS(matrix, p, q - 1);
    }
}
int findXShape(vector<vector<char>> &matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    int cnt = 0;
    for (int p = 0; p < matrix.size(); p++) {
        for (int q = 0; q < matrix[p].size(); q++) {
            // performing DFS on each element having a value 'X'
            if (matrix[p][q] == 'X') {
                cnt++;
                performDFS(matrix, p, q);
            }
        }
    }
    return cnt;
}
int main() {
    vector<vector<char>> matrix = {{'O', 'O', 'X'},
                                   {'O', 'X', 'X'},
                                   {'X', 'X', 'X'}};
    cout << "The total number of X shape in the given matrix is " << findXShape(matrix) << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int subArrSum(int nums[], int len, int k){
   int totalSum = 0;
   // Deques to store indices of the current window in increasing and decreasing order, respectively;
   deque<int> inc(k), dec(k);
   // Handling the first window
   int p = 0;
   for (p = 0; p < k; p++){
      // Remove elements which are greater than the current element
      while ((!inc.empty()) && nums[inc.back()] >= nums[p])
      inc.pop_back();
      // Remove elements from dec deque which are smaller than the current element
      while ((!dec.empty()) && nums[dec.back()] <= nums[p])
      dec.pop_back(); // Remove from rear
      // Add the nums[p] at last
      inc.push_back(p);
      dec.push_back(p);
   }
   // Hanlding other windows
   for (; p < len; p++){
      // get the first element from both the queues, and add them
      totalSum += nums[inc.front()] + nums[dec.front()];
      // Removing elements of the previous window
      while (!inc.empty() && inc.front() <= p - k)
      inc.pop_front();
      while (!dec.empty() && dec.front() <= p - k)
      dec.pop_front();
      while ((!inc.empty()) && nums[inc.back()] >= nums[p])
      inc.pop_back();
      while ((!dec.empty()) && nums[dec.back()] <= nums[p])
      dec.pop_back();
      inc.push_back(p);
      dec.push_back(p);
   }
   // Last window sum
   totalSum += nums[inc.front()] + nums[dec.front()];
   return totalSum;
}
int main() {
   int nums[] = {3, 5, -2, 6, 4, 8, -9, 10, -5};
   int len = sizeof(nums) / sizeof(nums[0]);
   int K = 4;
   cout << "The ans of minimum and maximum elements of all subarrays of size K is " << subArrSum(nums, len, K);
   return 0;
}