BUG: Rolling results with variable window may be incorrect

[ProV1denCEX]

Pandas version checks

• I have checked that this issue has not already been reported.

• I have confirmed this bug exists on the latest version of pandas.

• I have confirmed this bug exists on the main branch of pandas.

Reproducible Example

import pandas as pd
import numpy as np
from pandas.core.indexers.objects import BaseIndexer


class VariableWindowIndexer(BaseIndexer):
    def __init__(
            self,
            window_size_array: np.ndarray = None,
            **kwargs
    ):
        super(VariableWindowIndexer, self).__init__(**kwargs)
        self.window_size_array = window_size_array

    def get_window_bounds(self,
                          num_values: int = 0,
                          min_periods: int | None = None,
                          center: bool | None = None,
                          closed: str | None = None) -> tuple[np.ndarray, np.ndarray]:

        if center:
            raise NotImplementedError
        if closed is not None:
            raise NotImplementedError

        end = np.arange(1, num_values + 1, dtype="int64")
        sizes = self.window_size_array[:num_values]
        start = end - sizes

        loc = start < 0
        start[loc] = 0

        # start = start.astype(np.int64)

        # start = pd.Series(start).rolling(window=3, min_periods=1).min().astype(np.int64)
        # print("is_monotonic", start.is_monotonic)

        if isinstance(start, pd.Series):
            start = start.to_numpy()

        return start, end


n_row = 10000
n_col = 10

data = pd.DataFrame(np.random.random((n_row, n_col)), index=list(np.random.randint(3, 100, n_row)), columns=[str(i) for i in range(n_col)])

windows = np.random.randint(3, 10, n_row)
idx = VariableWindowIndexer(window_size_array=windows)
# idx = FixedWindowIndexer(window_size=10)

ret5 = data.rolling(window=idx)['0'].max()
ret6 = data.rolling(window=idx)['0'].apply(lambda x: x.max())

print((ret5 == ret6).all())

Issue Description

Rolling results like rolling.max/min are unreliable when rolling with variable window length. This issue occurs when start points of sub-windows are not monotonic increasing.

For example:
1st window's start / end: (4, 10)
2st windows' start / end: (2, 11)

In this case, due to the algo described in aggregations.pyx, the deque will drop data points between point 2 and 3, which should be counted in 2st window.

You can reproduce this issue in codes above and find the print is False in most case.
I understand the O(n) complexity and efficiency of the algo in aggregations.pyx. However this may cause potential calculation error. I think we should add an montonic check in the module to decide which algo should be utilized.

Expected Behavior

the expected result should be ret6 in codes above.

Installed Versions

INSTALLED VERSIONS

commit : 66e3805
python : 3.7.8.final.0
python-bits : 64
OS : Windows
OS-release : 10
Version : 10.0.18362
machine : AMD64
processor : Intel64 Family 6 Model 165 Stepping 5, GenuineIntel
byteorder : little
LC_ALL : None
LANG : None
LOCALE : None.None
pandas : 1.3.5
numpy : 1.19.5
pytz : 2021.1
dateutil : 2.8.1
pip : 21.0.1
setuptools : 54.0.0
Cython : 0.29.22
pytest : None
hypothesis : None
sphinx : None
blosc : None
feather : None
xlsxwriter : None
lxml.etree : 4.6.2
html5lib : None
pymysql : 1.0.2
psycopg2 : 2.8.6 (dt dec pq3 ext lo64)
jinja2 : 3.0.3
IPython : 7.21.0
pandas_datareader: None
bs4 : 4.9.3
bottleneck : 1.3.2
fsspec : None
fastparquet : None
gcsfs : None
matplotlib : 3.4.1
numexpr : 2.7.3
odfpy : None
openpyxl : 3.0.6
pandas_gbq : None
pyarrow : 2.0.0
pyxlsb : None
s3fs : None
scipy : 1.6.1
sqlalchemy : 1.3.23
tables : 3.6.1
tabulate : 0.8.9
xarray : None
xlrd : 2.0.1
xlwt : None
numba : 0.54.0

[mroeschke]

Thanks for the report. I think this is a duplicate of #46726 so closing in favor of centralizing the discussion there